Algorithm

Classic Binary Search

Binary Search Pattern

Binary Search

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, return its index. Otherwise, return -1. You must write an algorithm with O(log n) runtime complexity.

CONSTRAINTS
  • 1 <= nums.length <= 10^4
  • -10^4 < nums[i], target < 10^4
  • All the integers in nums are unique
  • nums is sorted in ascending order
EXAMPLE 1
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
9 exists in nums and its index is 4.
EXAMPLE 2
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
2 does not exist in nums so return -1.
Is the input array guaranteed to be sorted?
Yes, you can assume the array is sorted in ascending order before the search begins.
How should we handle a scenario where the target is not in the array?
If the target is missing, the function should return -1.

Searching for a number in a collection is like looking for a name in a massive phone book.

The Brute Force Struggle

The most natural way is a "Linear Search." You start on page 1 and flip through every page until you find the name.
- The Cost: If there are a billion names, you might have to check a billion pages. This takes O(N) time.
- The Inefficiency: This approach ignores the fact that the book is already sorted!

The Halving Discovery

Because the book is sorted A-Z, we can use a "Divide and Conquer" strategy.
1. Open the book exactly in the middle.
2. Compare the name there to our target.
3. The Decision: If our target comes "later" than the middle name, we know for a fact that the target cannot be in the first half of the book. We can throw away 50% of our work in just one second!

By repeating this process—always looking at the middle and discarding the impossible half—we narrow down a billion items to just one in about 30 steps. That is the magic of O(log N).

Code Blueprint
text
left = 0
right = length - 1

WHILE left <= right:
    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
Walkthrough:nums = [-1, 0, 3, 5, 9, 12], target = 9
Watch the search window shrink by half every step. The band you see below is everything still "in play" — once a comparison rules out a side, that side disappears from the next frame.
0
-1
1
0
2
3
mid
3
5
4
9
5
12
left=0, right=5, mid=2 → nums[2]=3 < 9. Target is to the right; discard the left half. left = mid+1 = 3
0
-1
1
0
2
3
3
5
4
9
mid
5
12
left=3, right=5, mid=4 → nums[4]=9 = target. Found!

Final Answer: 4

Why the Pattern is King

Binary Search is the ultimate optimization for sorted data. It transforms a task that could take minutes or hours (Linear Search) into a operation that finishes in microseconds. As long as you have a way to "discard half the options" based on a single comparison, Binary Search is the most efficient discovery tool in computer science.

Interactive Strategy Visualization

The Divide & Conquer Strategy

Binary search shrinks the search space by half in every step. It’s the difference between checking every book in a library and finding one in seconds.

Search Space12 items
2Left
5
8
12
16
23
38
45
56
72
81
99Right
🎯
Next Step: Locate the Center

Dividing the remaining 12 items to find the middle.

O(N) linear search
→
O(log N) binary search