Skip to main content

🟩 Binary Search (#704)

🔗 Problem Link​

📋 Problem Statement​

Given a sorted (in ascending order) integer array nums of n elements and a target value, write a function to search for target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

💡 Examples​

Example 1​

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2​

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

🔑 Key Insights & Approach​

Core Observation: In a sorted array, we can eliminate half of the remaining elements at each step by comparing the target with the middle element. This is the fundamental insight behind binary search.

Why Binary Search?

  • Exploits sorted property: Each comparison tells us which half to search
  • Logarithmic time: Divides search space in half each iteration - O(log n)
  • Better than linear: Beats O(n) sequential search dramatically for large arrays

The Mental Model: Think of guessing a number between 1-100. Each guess tells you "higher" or "lower." The optimal strategy is always guessing the middle value, cutting the search space in half each time.

Algorithm Steps:

  1. Initialize pointers: left = 0, right = len(nums) - 1
  2. While search space exists (left <= right):
    • Calculate middle: mid = left + (right - left) // 2
    • If nums[mid] == target: Found it, return mid
    • If nums[mid] < target: Search right half, set left = mid + 1
    • If nums[mid] > target: Search left half, set right = mid - 1
  3. Not found: Return -1

Critical Implementation Details:

  • Avoid overflow: Use mid = left + (right - left) // 2 instead of mid = (left + right) // 2
  • Loop condition: left <= right (inclusive) ensures we check when left equals right
  • Update pointers: Always use mid + 1 or mid - 1, never just mid (prevents infinite loops)

Pattern Recognition: This is the "Binary Search" pattern - whenever you have a sorted array and need O(log n) search, or when you need to find a boundary in a monotonic space.

🐍 Solution: Python​

Time Complexity: O(log n) | Space Complexity: O(1)

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

    while left <= right:
        # Calculate middle (avoids overflow)
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1  # Search right half
        else:
            right = mid - 1  # Search left half

    return -1  # Not found

Time Complexity: O(log n) | Space Complexity: O(log n) due to call stack

def search(nums: List[int], target: int) -> int:
    def binary_search(left: int, right: int) -> int:
        if left > right:
            return -1

        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            return binary_search(mid + 1, right)
        else:
            return binary_search(left, mid - 1)

    return binary_search(0, len(nums) - 1)

🔵 Solution: Golang​

Approach 1: Iterative Binary Search​

Time Complexity: O(log n) | Space Complexity: O(1)

func search(nums []int, target int) int {
    left, right := 0, len(nums)-1

    for left <= right {
        // Calculate middle (avoids overflow)
        mid := left + (right-left)/2

        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            left = mid + 1  // Search right half
        } else {
            right = mid - 1  // Search left half
        }
    }

    return -1  // Not found
}

Approach 2: Recursive Binary Search​

Time Complexity: O(log n) | Space Complexity: O(log n)

func search(nums []int, target int) int {
    return binarySearch(nums, target, 0, len(nums)-1)
}

func binarySearch(nums []int, target, left, right int) int {
    if left > right {
        return -1
    }

    mid := left + (right-left)/2

    if nums[mid] == target {
        return mid
    } else if nums[mid] < target {
        return binarySearch(nums, target, mid+1, right)
    } else {
        return binarySearch(nums, target, left, mid-1)
    }
}

📚 References​