LeetCode 704 ·
Easy
Binary Search
Return the index of target in a sorted array, or −1.
Try it
Step through the core mechanic. The simulator below runs the binary search shape this problem is built on.
Interactive · Binary search walkthrough Sorted array; halve the search range at each step.
0
-7
L
1
-3
2
0
3
2
4
5
5
8
6
11
7
14
8
17
9
21
10
25
11
30
H
start: lo=0, hi=11, mid=5, a[mid]=8
range12 log₂(n)≤ 4 step0 / 3
Why binary search is O(log n).
Each step halves the search range. Starting from
n, after
k steps the range is n / 2ᵏ; the search ends when
this drops below 1, so k ≤ log₂(n). For n = 10⁹,
that's ≤ 30 steps. The interview corollary: if the constraint is
n ≤ 10⁹, you need an O(log n) approach — binary search is
usually the one.The approach
Maintain a [lo, hi] range; compare the midpoint to the target and discard the half that cannot contain it. Use lo + (hi−lo)/2 to avoid overflow and a consistent loop invariant.
| Aspect | Value |
|---|---|
| Pattern | Binary search |
| Recognise it by | Sorted array, find a target in O(log n). |
| Time complexity | O(log n) |
| Space complexity | O(1) |
| Difficulty | Easy |
Who asks it
Companies known to ask this problem, from public LeetCode company-tag aggregations. A signal of where to expect it, not a guarantee.