Binary Search

Difficulty: Easy

Problem

A sorted array of integers nums and a value target are given. Report the index where target sits, or -1 when it is absent. Your solution must run in O(log n) time.

Example

Input: nums = [-7, -2, 0, 4, 11, 15, 21], target = 15
Output: 5
Explanation: 15 is stored at index 5, so that index is returned.

Brute-force approach

Scan every element from left to right until the target is found or the array is exhausted.

Steps

  1. For each index i from 0 to n-1:
  2. If nums[i] == target, return i
  3. If loop ends without finding target, return -1

Time complexity: O(n) · Space complexity: O(1)

Trade-offs

  • Checks every element. Doesn't use the sorted property at all
  • O(n) is too slow for large arrays when O(log n) is possible
  • For 1 billion elements, linear scan needs up to 1 billion checks vs ~30 for binary search

Optimal approach

Key insight: In a sorted array, one comparison with the middle element tells you which half the target must be in: instantly eliminating 50% of remaining elements. A subtle but critical detail: use mid = left + (right - left) / 2 instead of mid = (left + right) / 2 to avoid integer overflow.

Repeatedly compare the middle element with the target. If middle < target, search the right half. If middle > target, search the left half. Each step eliminates half the array.

Steps

  1. Set left = 0, right = n - 1
  2. While left <= right:
  3. mid = left + (right - left) / 2
  4. If nums[mid] == target: return mid
  5. If nums[mid] < target: left = mid + 1
  6. If nums[mid] > target: right = mid - 1
  7. Return -1 (not found)

Time complexity: O(log n) · Space complexity: O(1)

Pseudocode

function search(nums, target):
    left = 0
    right = len(nums) - 1
    
    while left <= right:
        mid = left + (right - left) / 2
        if nums[mid] == target:
            return mid
        else if nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

Hints

  • The array is sorted. Use this to eliminate half the search space each step
  • Compare the middle element with the target to decide which half to search
  • Use left + (right - left) / 2 to avoid integer overflow

Complexity questions

What is the time complexity of linear search on a sorted array?

O(n). Linear search checks each element one by one, so it's O(n) in the worst case.

What is the time complexity of binary search?

O(log n). Each step halves the search space. After k steps, the space is n/2^k. This reaches 1 when k = log2(n).

What is the space complexity of iterative binary search?

O(1). We only use three variables (left, right, mid), so it's O(1) space.

Check your understanding of Binary Search

Why does binary search require a sorted array?

A sorted array lets us eliminate half the elements by comparing the middle value with the target. In a sorted array, if the middle element is less than the target, ALL elements to the left are also less, so we can safely discard the entire left half. This halving only works because the array is sorted.

For nums = [1, 3, 5, 7, 9], target = 7, what is the first mid index checked?

2. left=0, right=4. mid = (0+4)/2 = 2. We check nums[2]=5 first. Since 5 < 7, we move left to mid+1=3.

How many elements does binary search check in the worst case for an array of 1000 elements?

About 10 (log2 of 1000). Binary search halves the search space each step. log2(1000) is about 10, so at most ~10 comparisons are needed. Far fewer than the 1000 checks linear search would need.

Related problems

Keep practising