Understanding Binary Search Algorithm
Atm of this writing, I'm following this DSA course, it's really good for the foundation knowledge in DSA stuff. Anyway, previously I never understand about binary search, but after watch the binary search section, I think I got it.
So basically, it's simply:
- divide the array into half
- get into the part that we predict will have the target
- divide it again into half
- get into the part that we predict will have the target
do it again until we find the desire target, but remember, binary search can only be used in sorted array, since we cannot predict that are we less or more than the desire target if the array is not sorted.
Since we split the array into half in every iteration, the time complexity will be O(log n), a significant improvement over O(n).
Example
I get the example from this leetcode question, it’s not exactly the same, but the idea is.
Question: Find if target exist in array arr, if exist return its index, else return -1
We could just loop through the entire array to find is the target exist or not, but that approach would give us O(n) in time complexity, which will grow linear as the size input, and not really good for large data. For the sake of this article, we will implement a better one (binary search)
Solution
Since we will divide the array into half, first we need to know the starting point (the zero index of the array) and the end point(the last item of the array). Notice that for hi variable, we are not assigning it to arr.length — 1 because we want to cover the case where the input array is only one item (for example: [3]).
Next we will do a loop to divide the array into half as long as the lo variable is less than hi, because if lo is equal or greater than hi, that mean the target is doesn't exist within the array.
First thing we want to do within the loop is we define the middle point of the array, which mean (lo + hi) / 2
Then well check if the current mid point is the target, then we successfully find the target and can return the index.
If not, well check if target is higher than the value of the current mid index, well update the lo variable to equal mid point + 1, since we know that the target is on the upper half of the array, so we don't care anymore about the lower half.
If the target is lower than the value of current mid index, well update the hi variable to equal mid point, because again, we know that the target is in the lower half of the array, so we don't care anymore about the upper half of the array.
If the loop doesn't return anything, which mean the target doesn't exist, we simply return -1.
Stackademic
Thank you for reading until the end. Before you go:
- Please consider clapping and following the writer! 👏
- Follow us on Twitter(X), LinkedIn, and YouTube.
- Visit Stackademic.com to find out more about how we are democratizing free programming education around the world.
