Bruce Banner a.k.a Hulk of DSA i.e. Binary Search

I believe there is hardly anyone who has not watched Avengers and is unfamiliar with the big green giant, THE HULK. You definitely know him in his human, normal form where he appears quite calm and introverted, never inclined to kill or argue with anyone. However, when he transforms into the HULK, he can destroy anything within seconds. So, in conclusion, I mean to convey that one should never underestimate a seemingly simple-looking human (algorithm in this case).

Binary Search

So now, let me discuss Binary Search. In actuality, it's a simple algorithm (Although the name seems to be scary), but it has vast applications. It's employed to search for an element in an array to have a time complexity of O(log N), where N represents the length of the array. Now, you might be wondering, '' Why the f*ck would I use Binary Search instead of the simpler Linear Search? '' The straightforward answer is that Binary Search utilizes O(log N) complexity, whereas Linear Search operates with O(N) complexity.

Example : Suppose you have an array of elements ranging from 1 to 1 million, and now you want to search for the element 1000001. In this case, your Linear Search will execute 1 million times, and it will return 'Not Found.' Meanwhile, Binary Search will yield the same result in log(1 million), i.e., in 6 executions. Now, you might have decided which algorithm is best, and if you are still in confusion about choosing the best algorithm, then trust me, your brain might have had a break-up with you.

Now after understanding the need of Binary Search let's see how we will be implementing it.

How To Implement Binary Search

1. So, firstly, remember that your array should be sorted either in ascending or descending order.

2. Set the starting point, which is the 0th index, and the ending point, which is mainly the index of the last element.

1. Now find the midpoint of the array using start and end point.

You must use the formula mid = start + (end - start)/2 which will prevent you from getting an error called integer overflow.

1. Now, comes two conditions for the 4th step, which are as follows :

   A. If number you are searching is greater than middle value of array then the number will defintely lie in 2nd half of array i.e. after middle value. In this case we will update start value as start = mid+1.

   B. If number you are searching is lesser than middle value of array then the number will defintely lie in 1st half of array i.e. before middle value. In this case we will update end value as end = mid-1.

2. Now we will repeat the process until we find the element we are looking for.

   Code

Here is the code of above algorithm in JAVA

As you can see in the above code I have followed all the steps as mentioned.

1. I have taken two variables named start and end and set them to 0 and the index of the last element, respectively.

1. Then there is a condition during the running of the while loop, i.e., (start < end), which means that the code will execute until the 'start' is less than 'end.' Sometimes, the condition might become (start <= end), which you will have to figure out according to the question.

2. Next we calculate the middle value.

3. Now we applied the conditions as stated above.

So that's all about Binary Search Algorithm. Now you might be wondering, " Where the hell I should use this algorithm ? ". So the short answer is "If the array is sorted then you should use Binary Search". So at last I'm adding some leetcode problems link in case you want to practice Binary Search.

LEETCODE Problem Number :

704, 1608, 852, 35, 374, 278, 367.