Binary Search

You are given an array nums of distinct integers sorted in ascending order, and an integer target.

Return the index of target in nums, or -1 if it does not appear. Your algorithm should take O(log n) time, so scanning the array element by element is not the intended solution.

Example 1

Example 2

Example 3

Constraints

• 1 <= nums.length <= 104
• -104 < nums[i], target < 104
• All values in nums are distinct and sorted in ascending order.

Pattern Path · Binary Search · problem 57 of 169

Start simple

Scan from left to right until you find the target or pass it: O(n) time, O(1) space.

The key idea

Sorting gives every comparison a lot of power. If nums[mid] < target, then every element at or before mid is also too small, so half of the remaining candidates can be thrown away at once. If nums[mid] > target, everything at or after mid is too big.

Maintain an inclusive window [lo, hi] with the invariant "if the target exists, its index is inside the window". Start with the whole array. Each step checks the middle element: return it on a match, otherwise move lo to mid + 1 or hi to mid - 1. Both moves exclude mid, so the window always shrinks and the loop always ends.

When lo > hi the window is empty, and by the invariant the target is absent, so return -1. Halving the window each time means at most about log₂(n) + 1 iterations: around 14 for ten thousand elements.

Complexity

• Time: O(log n)
• Space: O(1)

Python

class Solution:
    def search(self, nums, target):
        lo, hi = 0, len(nums) - 1   # if target exists, it is in nums[lo..hi]
        while lo <= hi:
            mid = (lo + hi) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] < target:
                lo = mid + 1        # target can only be to the right
            else:
                hi = mid - 1        # target can only be to the left
        return -1

JavaScript

var search = function(nums, target) {
  let lo = 0;
  let hi = nums.length - 1;  // if target exists, it is in nums[lo..hi]
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) {
      lo = mid + 1;          // target can only be to the right
    } else {
      hi = mid - 1;          // target can only be to the left
    }
  }
  return -1;
};

What the interviewer is checking

Binary search is easy to describe and easy to get wrong. The interviewer is watching your loop invariant, your boundary updates and your termination condition.

Mistakes to avoid

• Using while lo < hi with an inclusive hi, which never checks the last remaining element.
• Setting lo = mid or hi = mid with an inclusive window, which can loop forever on two elements.
• Computing (lo + hi) / 2 with fixed-width integers in very large arrays can overflow; lo + (hi - lo) / 2 is safe.

Follow-ups to expect

• What if values can repeat and you need the first occurrence? (Keep searching left after a match.)
• What if the sorted array was rotated? (Decide which half is sorted first.)
• What if the array size is unknown? (Double the bound, then binary search.)

In real software

Database indexes, sorted file formats and tools like git bisect all rely on halving a sorted search space to find an item or the first failing change.

Practice next