Binary search

In a naive, or sequential search for some item in a list, each element must be visited. If however the list is sorted, a binary search may instead be used to recursively divide and conquer.

A binary search works over a sorted list of inputs. It compares against the middle element then recurses into either the left or right sub-lists as required, halving the search space with each iteration.

The structure of this style of search may also be modelled by a Binary search tree.

Algorithm

IF list is empty
   RETURN unsuccesful
ELSE
    x ← middle element
    IF x = item
        RETURN success (or item, or index)
    ELSE IF x > item
        recurse into left sublist
    ELSE
        recurse into right sublist

Performance