Binary Search
Sometimes you have a sorted array and you want to know if a certain number is present in the array. Searching through an array is a lengthy process. Without knowing where an element is located you must check each element to see if it’s the one you’re looking for – a search taking linear time O(n) where n is the number of elements. It’s pretty easy to see that this gets out of hand when managing large arrays of data.
The bright side is, if you’re dealing with a sorted array, there is a better way to search! Binary search is a searching algorithm that drastically reduces the amount of time it takes to search an array (from O(n) to O(log(n))). This is accomplished by continually halving the portion of the array to be searched until the element is found. This blog post will break down the iterative and recursive approach to the binary search method.
Both approaches have the same basic steps. For each pass through the loop or function find the middle point and compare the value at the to the target. If the target is higher than the middle point discard the lower half of the collection and run the loop again with the upper half. If the target is lower than the middle, discard the upper half and repeat the loop. This can be repeated until the middle and target are equal or until the collection has been exhausted without finding the target.
Let’s code!
The function will either return the index of the position of target in the array or -1, indicating that target is not in the array.
Method 1:
The recursive method is very similar, but the recursive function takes the high and low point as parameters in addition to the array and the target.
Method 2:
As a recap, this is a much more efficient way to search through a sorted array. Instead of looking at each element, half of the collection is tossed each time you search and this reduces the time complexity from O(n) to O(log(n)).