In a previous blog, I wrote about an effective way to sort an array. However, what if you need to find a specific element in an array after it has been sorted? Well, one way to do that is with binary search, so let's check it out and see how it works.
What is it?
Binary search is a search algorithm that, as mentioned above, helps you find an element in a sorted array. Unfortunately, it only works with sorted arrays. This search algorithm is much faster compared to linear search, which counts each element one at a time.
How does it work?
The reason binary search is so much faster than linear search is that it takes the array and halves it at the array’s midpoint. It then determines if the target value is greater than the midpoint value, and if it is, it removes the lesser half from the equation. This process repeats until the target value has been found. Below is an example of a coded out binary search:
We give the function the array, our target value, and two variables start and end. We set start to 0 and end equal to the length of the array minus 1 to account for index 0. We then define a variable called mid, which is our array halved. If that is our target value, then we return true. If not, we check to see if it is greater than or less than our target. If it’s greater than our target, we recursively use our function again but with mid minus 1 as our end. The same is true if mid is less than x, but we use mid plus 1 instead and use that as our start instead of our end.
That’s binary search in a nutshell! Use this if you need a target value in a sorted array but need to do it faster than linear time complexity. Hope this helps.
