Binary Search

  # 1. Binary Search: Search in Sorted Array
  # Problem Statement:
  # Given a sorted array of integers and a target value, return the index if the target is found.
  # Otherwise, return -1.
  # Input: nums = [-1,0,3,5,9,12], target = 9
  # Output: 4
  # Time Complexity: O(log n)
  def self.binary_search(nums, target)
    left, right = 0, nums.size - 1

    while left <= right
      mid = left + (right - left) / 2
      puts "Debug: left=#{left}, right=#{right}, mid=#{mid}, nums[mid]=#{nums[mid]}"
      if nums[mid] == target
        return mid
      elsif nums[mid] < target
        left = mid + 1
      else
        right = mid - 1
      end
    end

    -1