Binary Search is a search algorithm that finds a value within a sorted array or list. Binary search runs in at worst logarithmic time, making O(log n) comparisons. It does this by first looking at the middle element of the list. If the value (the value you are searching for) is not equal to this middle element, the value must be higher or lower than that middle element. If the value is lower, we can eliminate the entire right half of the list (the opposite if the value is higher). This process is repeated until the value is found.

Here is a nice gif that shows binary search vs sequential search on the same sorted list:

Below, I have implementations in both Python and Ruby. Both include iterative and recursive solutions:

Python:

Ruby: