Binary search: definition
Binary search repeatedly halves an ordered search range. Compare the middle value with the target, then keep only the side that can still contain the answer.
Problems this pattern can solve
- Find a value or insertion position in a sorted array
- Find boundaries, such as the first and last occurrence
- Search for the minimum feasible shipping capacity
- Find the kth smallest value in a row-and-column sorted matrix
For answer-space problems, the feasibility test must be monotonic: once a candidate works, all candidates on one side must work too.
Task example: Binary Search
In a strictly increasing integer array nums, find target and return its zero-based index. Return -1 when it is absent. Keep nums unchanged. The required solution runs in O(log n) time; the linear scan below is a baseline for comparison.
The values are distinct and already sorted. In the first example, 9 is at index 4. The second target, 2, is missing.
Linear scan: video explanation
nums = [-1, 0, 3, 5, 9, 12], target = 9 → 4
Prefer reading? Follow the steps below.
- Visit indices from left to right. Compare nums[i] with target at each position.
- Return i immediately when they match. For target 9, indices 0, 1, 2, and 3 fail; index 4 matches.
- Return -1 only after the loop finishes without a match. Placing that return inside the loop would stop after the first mismatch.
Time complexity · O(n)
In the worst case, the scan checks all n values. A match at the first index takes O(1) time.
Space complexity · O(1)
Only the loop index is stored. No extra array or recursion is used.
Binary search: video explanation
nums = [-1, 0, 3, 5, 9, 12], target = 9 → 4
Prefer reading? Follow the steps below.
- Set left = 0 and right = len(nums) - 1. These inclusive boundaries contain every position where the target can still be.
- While left <= right, compute mid = left + (right - left) // 2. If nums[mid] matches, return mid.
- If nums[mid] is smaller, set left = mid + 1. If it is larger, set right = mid - 1. Sorted order proves that the discarded side cannot contain target.
- If left passes right, no candidates remain: return -1. The +1 and -1 updates exclude the checked middle and guarantee progress.
For target 9, check index 2 (value 3), then index 4 (value 9). Binary search uses two comparisons here, while the linear scan uses five.
Time complexity · O(log n)
Each unsuccessful comparison roughly halves the remaining range. At most O(log n) iterations are needed; an immediate middle match is O(1).
Space complexity · O(1)
This iterative solution stores left, right, and mid. It creates no subarrays and uses no recursive call stack.