A binary search is an O(ln(n)) searching algorithm which searches for an object by examining the middle entry and

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

All implementations use the formula a + (b - a)/2 to calculate the middle entry as opposed to (a + b)/2 as the second 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.