Binary Search Algorithms
One Of The Quickest Ways Of Searching Through Data
“Binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array.”¹. It’s important that the array is already sorted, or steps will need to be taken to first sort the array before proceeding.
Let’s start building our function: We have our array which we will list as the variable ‘arr’. The element that we are in search of will be listed as a variable named ‘target’. When we first create our search function, we will set variables for 2 different pointers, a left pointer and a right pointer. Something very common, when encountering this algorithm, is that you’ll be asked to return (-1) if the element that you are looking for is not included in the array. The edge case of the array being empty, is handled with this return value being (-1).
If our return value is (-1) above, then we’ll need to include the logic for if our element IS included in the array. We will set up a loop to move the pointers on the array while we search for our target, if it exists in the array. We will only want to stay in our array if the left pointer is at a position either less than or equal to the position of the right pointer, we never want the pointers to cross. It’s important to immediately find the median of the array. We know that if the array at the index of median is the same as the target, we can return the median (med).
If the arr[med] does not have the same value as our target, we can now decide which side of the array we need to check for the value. We know that if arr[med] is greater than our target, we only need to check the half of the array to the left of the median. If arr[med] is less than our target value, then we only we need to check the right side of our array from that median.
The way to only search the left half of the array is to move the position of the right pointer to the left of median. We don’t need the median to be in our array anymore, bc it’s not our target, so you’ll see in line 15 above rightPointer now equals med-1. If we need to search the right side of the array, instead we will move our left pointer to the index in the array 1 position after the median, see line 19 above.
We’ll continue iterating in the while loop, each time dividing our search in the array by half. If we find our array[med] value ever becomes our target value, we return our median, otherwise we’ll exit the while loop bc our pointers cross and we return -1 because the target was never found. Each of the loops will look like this:
The algorithm using Binary Search has a Big O time complexity of O(log n). Except when discussing very small arrays, Binary Search is faster than linear search O(n).
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
- Binary Search Algorithm | Wikipedia | “https://en.wikipedia.org/wiki/Binary_search_algorithm”
