A quarter search is an O(ln(n)) searching algorithm which searches for an object by examining the entry either one quarter or three quarters into the array based whether the object being searched for is closer to the first or last entry.

• Returning true if that is the object being searched for; or
• Either examining the first half if the object is less than the chosen entry, or
• Examining the second half if the object is greater than the chosen entry.

All implementations use the formula a + (b - a)/4 or b - (a - b)/4 to calculate the appropriate entry as opposed to a formula such as as opposed to, for example, (a + 3*b)/2, as this formula is subject to overflow.

The basic implementation does exactly this using a recursive algorithm.

The enhanced array-based implementation:

• Uses an iterative form of the implementation,
• Calls a linear search algorithm if the interval being searched is of width 18 or less—the overhead of recalculating the centre multiple times is greater than just walking through the eighteen entries using a linear search,
• Has a front end which checks if the entry being searched for is outside the bounds of the array.

The enhanced pointer-based implementation uses the same enhancements used with the binary search algorithm.

Assuming that a list is approximately uniformly ordered, this algorithm has the fastest convergence without resorting to the floating-point calculations required with, for example the interpolation search.

Comparison with Binary Search

The average number of iterations necessary for a binary search is lg(n + 1)(1 + 1/n) - 1; however, the average number of searches for a quarter search is approximately ln(n) - 0.5. This reduces the expected number of searches by a factor of 0.693 or ln(2). Figure 1 shows the function ln(n) - 0.5 (blue), lg(n + 1)(1 + 1/n) - 1 (red), and the actual average number of searches in a uniform list for lists of size up to 1000 (black).

Figure 1. A comparison of theoretical average-number of searches for binary search (red) and quarter search (blue) together with the actual data for quarter search.

If the data is not uniformly distributed, the performance will be worse than that of a binary search.

A factor of 1/4 is apparently not the optimal value to choose; however, almost any other value requires floating-point computations which would seriously reduce the usefulness.