Binary Search

Overview

Binary Search is an efficient search algorithm that finds a target value within a sorted array. It works by repeatedly dividing the search space in half, eliminating half of the remaining elements with each comparison.

Key Requirement

The array must be sorted for binary search to work correctly.

Algorithm Steps

Initialize two pointers: left at start, right at end of array
While left <= right:
- Calculate mid as the middle index
- If A[mid] == target, return mid
- If A[mid] < target, search right half (left = mid + 1)
- If A[mid] > target, search left half (right = mid - 1)
If not found, return -1

Complexity

Metric	Complexity	Reason
Time Complexity	$O(\log n)$	Halves search space each step
Space Complexity	$O(1)$	Only uses constant variables

Implementation

def bs(A: List[int], target: int) -> int:
    left, right = 0, len(A) - 1

    while left <= right:
        mid = left + (right - left) // 2  # Avoids overflow
        if A[mid] < target:
            left = mid + 1
        elif A[mid] > target:
            right = mid - 1
        else:
            return mid

    return -1

Example

A = [1, 3, 5, 7, 9, 11, 13]
target = 7

# Step 1: left=0, right=6, mid=3, A[3]=7 == target
# Found at index 3

result = bs(A, 7)  # Returns 3
result = bs(A, 4)  # Returns -1 (not found)

Key Points

Requires sorted array as a precondition

Avoid Integer Overflow

Use left + (right - left) // 2 instead of (left + right) // 2 to avoid overflow.

left <= right includes the case where the search space is a single element
Can be adapted for finding insertion points, first/last occurrence, or boundary conditions

33. Search in Rotated Sorted Array