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
Worked Example:Target 9 in [-1, 0, 3, 5, 9, 12]
1. Start: left=0, right=5. mid=(0+5)/2 = 2. nums[2] is 3.
2. 3 < 9: Target must be to the right. Set left = 3.
3. Next: left=3, right=5. mid=(3+5)/2 = 4. nums[4] is 9.
4. Match! return 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