Easy
ArrayBinary Search
Updated Sep 2026

Binary Search

Asked at Meta

Problem

Implement binary search to find a target value in a sorted array and return its index, or -1 if not found. This is the foundational algorithm for the binary search pattern. Most interviewers expect you to know this cold, and it's the basis for dozens of harder problems.

Asked At

CompanyDifficulty
MetaEasyView all Meta questions →

How to Think About It

1.

Binary search works on sorted arrays by repeatedly dividing the search space in half. Compare target with the middle element: if equal, found. If target < mid, search left half. If target > mid, search right half.

2.

The standard template: two pointers left = 0 and right = n - 1. While left <= right, compute mid = left + (right - left) // 2 (avoids overflow). Compare and narrow the range.

3.

Why left + (right - left) // 2 instead of (left + right) // 2? Integer overflow. If left and right are both near INT_MAX, their sum overflows. The subtraction form is safe.

4.

Visual walkthrough: nums = [-1, 0, 3, 5, 9, 12], target = 9.

  • left=0, right=5, mid=2, nums[2]=3 < 9. Go right: left=3.
  • left=3, right=5, mid=4, nums[4]=9 == 9. Found! Return 4.

Visual walkthrough: nums same, target = 2.

  • left=0, right=5, mid=2, nums[2]=3 > 2. Go left: right=1.
  • left=0, right=1, mid=0, nums[0]=-1 < 2. Go right: left=1.
  • left=1, right=1, mid=1, nums[1]=0 < 2. Go right: left=2.
  • left=2, right=1. Loop ends. Return -1.
5.

Common pitfalls: using left < right instead of left <= right (misses single element), forgetting to move pointers past mid (infinite loop), and using mid = (left + right) / 2 (overflow).

6.

Time: O(log n) because the search space halves each iteration. Space: O(1) iterative. Recursive is O(log n) stack space but unnecessary.

Optimal Approach

Standard binary search:

  1. Set left = 0, right = n - 1.
  2. While left <= right:
    a. mid = left + (right - left) // 2
    b. If nums[mid] == target, return mid.
    c. If nums[mid] < target, set left = mid + 1.
    d. If nums[mid] > target, set right = mid - 1.
  3. Return -1.

Walkthrough: nums = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91], target = 23.

  • left=0, right=9, mid=4, nums[4]=16 < 23. left=5.
  • left=5, right=9, mid=7, nums[7]=56 > 23. right=6.
  • left=5, right=6, mid=5, nums[5]=23 == 23. Return 5.

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

What Trips People Up in Real Interviews

1.

Using left < right instead of left <= right. The < version misses the case where left == right (single element). Use <= for the standard search. Use < only for specific variants like finding the leftmost insertion point.

2.

Forgetting to add 1 or subtract 1 when narrowing the range. After comparing with mid, you must set left = mid + 1 or right = mid - 1. If you set left = mid or right = mid, you get an infinite loop when left == right.

3.

Not using mid = left + (right - left) // 2. While (left + right) // 2 works for small arrays, it overflows for large indices. Use the safe form by default.

4.

Assuming the array is sorted. Binary search REQUIRES sorted input. If the array isn't sorted, you must sort first (O(n log n)) or use a hash map (O(n)). Always confirm the input is sorted.

5.

Not handling the not-found case. After the loop exits, if you haven't returned mid, the target doesn't exist. Return -1. Don't return left or right, as those represent insertion points, not found indices.

Solution Code

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

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Binary Search problem?

Implement binary search to find a target value in a sorted array and return its index, or -1 if not found. This is the foundational algorithm for the binary search pattern. Most interviewers expect you to know this cold, and it's the basis for dozens of harder problems.

How do you solve Binary Search?

The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.

What companies ask Binary Search?

Binary Search is asked at Meta. It is a easy difficulty problem.

What are common mistakes on Binary Search?
  • Using `left < right` instead of `left <= right`. The `<` version misses the case where left == right (single element). Use `<=` for the standard search. Use `<` only for specific variants like finding the leftmost insertion point.
  • Forgetting to add 1 or subtract 1 when narrowing the range. After comparing with mid, you must set `left = mid + 1` or `right = mid - 1`. If you set `left = mid` or `right = mid`, you get an infinite loop when left == right.
  • Not using `mid = left + (right - left) // 2`. While `(left + right) // 2` works for small arrays, it overflows for large indices. Use the safe form by default.
  • Assuming the array is sorted. Binary search REQUIRES sorted input. If the array isn't sorted, you must sort first (`O(n log n)`) or use a `hash map` (`O(n)`). Always confirm the input is sorted.
  • Not handling the not-found case. After the loop exits, if you haven't returned mid, the target doesn't exist. Return -1. Don't return left or right, as those represent insertion points, not found indices.