Lower and upper bound
Plain binary search stops at any match. These two keep going: lower bound finds the first index that is at least the target, upper bound the first that is past it. Between them sits every copy.
1335555899
Find where the run of 5s starts and ends. Press play or step forward to start.
1function lowerBound(a, target) {2 let lo = 0, hi = a.length;3 while (lo < hi) {4 const mid = Math.floor((lo + hi) / 2);5 if (a[mid] < target) lo = mid + 1;6 else hi = mid;7 }8 return lo;9}1011function upperBound(a, target) {12 let lo = 0, hi = a.length;13 while (lo < hi) {14 const mid = Math.floor((lo + hi) / 2);15 if (target < a[mid]) hi = mid;16 else lo = mid + 1;17 }18 return lo;19}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | log n | every input: each search always runs to lo = hi |
| average | log n | any target |
| worst | log n | even a run of a million copies costs about 40 probes for both bounds |
| space | 1 | just lo, mid and hi |
Where it breaks
- Unsorted input. Same as binary search: the method rests on everything to the left being smaller. On unsorted data the bounds are meaningless.
- The half-open range. Here
histarts ata.length, one past the end, and the loop islo < hi. That lets the answer be "past the end" when every value is smaller. Mixing inhi = a.length - 1orlo <= hibreaks it. - A missing target is not an error. Pick Missing 6: both bounds land on 7, where 6 would be inserted to keep the array sorted. The count, upper minus lower, is 0.