Guessing the right page instead of always opening the middle

Binary search commits to the middle, always

CS105ES's binary search always checks the exact midpoint of the current range, no matter what the values look like. That is a safe, simple default — but it ignores useful information sitting right there in the data: if the target is close to the low end of the range, the answer is probably near the low end too, not exactly in the middle.

Interpolation search: like flipping straight to Z in a dictionary

When you look up a word starting with Z in a physical dictionary, you do not open to the middle — you flip almost to the end, because you know roughly where Z words live relative to the whole alphabet. Interpolation search does exactly this arithmetically: instead of always checking the midpoint, it estimates a position proportional to where the target should fall between the current low and high values.

On data spread out evenly — like roll numbers or timestamps — this estimate lands very close to the real answer almost every time, needing far fewer comparisons than binary search's blind midpoint. On unevenly clustered data, the estimate can be badly wrong, and interpolation search can degrade to checking nearly every element — worse than binary search, not better.

int pos = low + (int) (((double) (target - arr[low]) * (high - low))
                        / (arr[high] - arr[low]));

/* pos == low   when target == arr[low]  */
/* pos == high  when target == arr[high] */
/* pos in between, proportionally, otherwise */

Jump search: skim by chapter, then read the page

Skimming a textbook for a topic, you do not check every page — you jump by chapter heading first, find the right chapter, then read page by page within it. Jump search does this on a sorted array: check every k-th element until one exceeds the target, then switch to a plain linear scan across just that one block.

The block size that minimizes total comparisons works out to the square root of the array's length — jumping by roughly the square root balances the cost of the jumping phase against the cost of the linear phase. It never beats binary search on comparison count, but it makes only one direction of movement, backward jumps never happen, which matters on hardware where jumping backward through data is more expensive than moving steadily forward.