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.
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
|Time||\(O(\log n)\)||\(O(\log n)\)||\(O(1)\)|