Basic Binary Search

Problem Statement

Given a sorted array nums and a target value target, return the index of target in nums. If target does not exist, return -1.

Example: nums = [1,3,5,7,9], target = 5 → Output: 2

Approach 1: Iterative Binary Search

Explanation: Use two pointers (low & high) to narrow down the search space iteratively.

Time Complexity: O(log n)

Space Complexity: O(1)

low = 0
high = n - 1
while low <= high:
    mid = (low + high) // 2
    if nums[mid] == target:
        return mid
    else if nums[mid] < target:
        low = mid + 1
    else:
        high = mid - 1
return -1

Approach 2: Recursive Binary Search

Explanation: Recursively divide array to find target.

Time Complexity: O(log n)

Space Complexity: O(log n) (due to recursion stack)

function binarySearch(nums, low, high, target):
    if low > high:
        return -1
    mid = (low + high) // 2
    if nums[mid] == target:
        return mid
    else if nums[mid] < target:
        return binarySearch(nums, mid+1, high, target)
    else:
        return binarySearch(nums, low, mid-1, target)

Approach 3: Using Built-in Language Functions (Optional)

Explanation: Many languages have built-in functions for binary search, e.g., bisect in Python, Arrays.binarySearch in Java.

Time Complexity: O(log n)

Space Complexity: O(1)

// Python example
import bisect
index = bisect.bisect_left(nums, target)
if index < len(nums) and nums[index] == target:
    return index
else:
    return -1