โ† DSA I

Binary Search

Predict how the search range shrinks, one line at a time.

โšก 0 XP
Presets

2โ€“16 sorted integers. Duplicate values are allowed.

1int left = 0, right = values.size() - 1;
2while (left <= right) {
3 int mid = left + (right - left) / 2;
4 if (values[mid] == target) return mid;
5 if (values[mid] < target) left = mid + 1;
6 if (values[mid] > target) right = mid - 1;
7}
8return -1;
Memory viewTarget 23
02L
15
28
312
416
523
638
756R

โ— Active rangeโ— Midpointโ— Discarded

1 / 9
0 comparisons3 max halving roundsO(log n) timeO(1) space