Interpolation Search
Learn Interpolation Search (Searching, Data Structures & Algorithms) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.
Guessing WHERE the Target Probably Is Binary search always checks the MIDDLE, regardless of the target's value. Interpolation search does better on UNIFORMLY DISTRIBUTED sorted data by estimating a smarter probe position - like flipping to the right page in a phone book directly, instead of always opening to the middle first. probe = low + (target - arr[low]) * (high - low) / (arr[high] - arr[low])