Loading...
Retrieval is the backbone of interaction. Master the search strategies that find a needle in a haystack of billions in just dozens of steps.
The "Gold Standard" for finding data in sorted arrays. By eliminating half the search space at every step, it reduces linear work to logarithmic work.
To search 1 Billion items, you only need ~30 comparisons.
Avoid (L+R)/2. Use L + (R-L)/2 to prevent potential memory overflows in large systems.
1function binarySearch(arr, target):2 L = 0, R = arr.length - 13 4 while L <= R:5 mid = L + floor((R - L) / 2)6 7 if arr[mid] == target:8 return mid9 10 if arr[mid] < target:11 L = mid + 112 else:13 R = mid - 114 15 return -1When the target matches arr[mid], don't stop. Search the left half to see if a previous occurrence exists.
Finds the first element that is not less than the target. Essential for std::lower_bound logic.
Like finding a name in a phone book. If you're looking for "Z", you start near the end. If the data is uniformly distributed, this search hits $O(\log \log n)$ performance.
// The Estimation Formula