Binary search:

It's a search algorithm used with sorted arrays/lists to find a target value by dividing the array each iteration and comparing the middle value to the target value. If the middle value is smaller than target value, then the target value is searched in the right part of the divided array, else in the left side. This continues until the value is found (or the array divided max times)

python implementation

The average performance of the above algorithm is O(log n). Best performance can be O(1) and worst O(log n).