ToolMight LogoToolMight
EasyBinary SearchPattern: Divide and ConquerPattern: Two Pointers

Binary Search

Locate a target value in a sorted array in O(log n) logarithmic time. Like opening a dictionary in the middle, each comparison eliminates half the remaining items.

Problem Statement

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, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Examples & Constraints

Example 1
Input: nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4.
Example 2
Input: nums = [-1, 0, 3, 5, 9, 12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1.
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.

Select Approach (2 Solutions)

Iterative Binary Search (Boundary Division)

Optimal Approach
Time:O(log n)
Space:O(1)

Maintain left and right boundaries, calculate the midpoint, and eliminate half the search space on each comparison.

Time ComplexityO(log n)

At each step, the search window size is divided by 2. After k steps, window size is n / 2^k = 1, giving k = log2(n).

Space ComplexityO(1)

Only three integer pointer variables (left, right, mid) are stored in memory.

Underlying algorithmic logic

The Core Mental Model: The Phonebook / Dictionary Trick

If you want to find the word "Mango" in an alphabetical dictionary of 1,000 pages, you don't start at page 1 and read every word (that's Linear Search).

Instead, you open the book right around the middle (page 500). If you land on "Pineapple", you know with 100% certainty that "Mango" can only exist in the first 500 pages. You just discarded 500 pages with one glance!

Key Engineering Invariants & Gotchas

  1. The Invariant: `[left, right]` Closed Interval:
  • left = 0, right = nums.length - 1.
  • The loop condition must be `while (left <= right)`.
  • Why `<=` instead of `<`? When left == right, exactly one candidate element remains. If you used <, that last element would never be checked!
  1. The Classic Integer Overflow Bug:
  • In C, C++, and Java, writing mid = (left + right) / 2 can cause a catastrophic bug. If left + right exceeds 2^31 - 1 (2,147,483,647), it overflows into a negative number, crashing with an out-of-bounds index.
  • Always write: mid = left + (right - left) / 2.
  1. Narrowing the Boundaries:
  • If nums[mid] == target, target found -> return mid.
  • If nums[mid] < target, the target must be strictly to the right -> left = mid + 1.
  • If nums[mid] > target, the target must be strictly to the left -> right = mid - 1.
  • If left > right, the search interval is exhausted and the target is missing -> return -1.

Step-by-step execution walkthrough

1
Initialize Pointers

left = 0, right = 5 (nums = [-1, 0, 3, 5, 9, 12]).

left = 0, right = 5
2
First Division

mid = 0 + (5-0)/2 = 2. nums[2] is 3. 3 < 9, so target is to the right. Set left = 3.

left = 3, right = 5
3
Second Division

mid = 3 + (5-3)/2 = 4. nums[4] is 9. 9 == 9 -> Target found!

mid = 4 -> return 4
Advantages
  • •Optimal O(log n) efficiency
  • •Minimal O(1) memory footprint
  • •Eliminates call stack overhead
Trade-offs
  • •Array must be sorted beforehand
  • •Requires careful midpoint overflow handling

Code Implementations

Copy & paste production-ready solutions for Iterative Binary Search (Boundary Division) in your language of choice

File: solution.py
Python
def search(nums: list[int], target: int) -> int:
    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
if __name__ == "__main__":
    nums = [-1, 0, 3, 5, 9, 12]
    target = 9
    print(f"Target {target} found at index: {search(nums, target)}")
Interactive visualizer available

Understand Binary Search Visually

Divide and conquer sorted datasets, converging left/right indices to isolate target values. Test live edge cases and watch memory state transitions step-by-step.

Launch Binary Search Visualizer

Frequently Asked Questions

Related Logic & Algorithm Problems

All problems
EasyArrays & Hashing
Visualizer

Linear Search

The foundational search algorithm for unsorted collections. Scans elements one by one until a match is found or the list is exhausted.

2 approaches(O(n))
Learn logic
MediumBinary Search
Visualizer

Search in Rotated Sorted Array

Search a rotated sorted array in O(log n) time. A masterclass in applying binary search when global order is broken: at least one half is always guaranteed to be sorted.

1 approach(O(log n))
Learn logic
EasyArrays & Hashing
Visualizer

Two Sum

Find the two numbers in an array that sum up to a target value. The quintessential problem for learning how to trade memory for speed using a Hash Map.

2 approaches(O(n))
Learn logic