Binary search is a fantastic algorithm for finding elements in an ordered list (or array) of items. It works by repeatedly dividing the search space in half. It starts with a middle element and compares it against your key. If the search value is smaller than the middle element, algorithm skips the second part of an array.
The process repeats until the algorithm gets the right value. It’s crucial that the array is already sorted for this algorithm to work.
Given the search space is halfed every iteration,
Big O and the worst case scenario is
O(log n) where
n is the total number of elements. Algorithm doesn’t depend on the number of elements so the space complexity is
Binary search works the same for almost all inputs and the only different parameter is the search space so it should be fairly easy to make both recursive and iterative solutions.
Iterative version written in Ruby:
Recursive version written in Ruby:
Also, Wikipedia has a great image which shows how the number 7 is found inside an array:
From Wikipedia: Visualization of the binary search algorithm where 7 is the target value