Now that you have learnt what binary search is, let’s look at the Java implementation of the algorithm. But before we move onto the Java implementation, let's first discuss the pseudocode of the algorithm.

$$/$$

Video Transcript

So now we'll take a look at a simple pseudocode for binary search and try to relate it with the example we already discussed. So if you look here carefully, you would see that my function binary will take in two inputs which is a and t which denotes the array and the element t, which I want to find whether it exists in the array or no. So here I have defined some variables. Variable n denotes the length of the array. My variable start denotes the starting index of the current array which I'll be considering. I'll be initializing it with zero here and another variable end, which will be initialized to the last index of the array which is n minus one. So let me relate it to the example here. So in my case, my starting index would be this one and my ending index would be this one. Now, let us move and see this step here. What I am doing is that I'm finding the middle element of the array by calculating the mid index here. Mid denotes the middle index of the entire array which will be equal

to start plus end by two. Now, in my case, my mid index would be this one, which will be the fifth index. Now, in the next step, what I am doing is that I have three if else conditions and I'm comparing my middle value with the value which I want to find, which is my target value. So in my case, I would see and compare my target value with the mid value. In this case, my mid value equals to 16 and my target value equals to 23. So in the first if loop, I would check whether t equals to equals to amid, that is whether 23 is equal to equal to 16. Since this is not true, I move on to my next if condition. My next if condition says to check if amid is less than t here t is equal to x, which is my target value which is 23, and amid is 16. Since t is greater than amid. I would go into this if condition and update my start index to mid plus one. So this is what is happening actually in step number two. Let us revisit. My starting index was here, ending index was here and mid index was here. I was

comparing my target value with the value at the middle index. I found out that my target value is greater than the mid value. So what I'll do in this step, I'm updating my start pointer to mid plus one here. Mid was here. So what I'll do in my next step, my start value will come here, which is mid plus one. This you can clearly see in this step, which is step number two. Now, the array which I'll be considering is this one. This will denote the start index and this would denote my ending index. Again, notice that the start index was updated to mid plus one. And so that is why the array which I'll be considering in this step would be this one. I'll be repeating the same procedure again. I would again calculate my mid index for this particular array here. My start index is here, and ending index is here. So my mid index would be start plus end by two. Since there are five elements here, my mid index would be this one. Now, again, I'll be going into three FL conditions and check which one

of them holds. Again, my target value is 23 and my amid value, which is the middle value, is 56. Certainly they both are not equal. I would go into my next if loop and see whether amid is less than t here. Amid is 56, which is the middle value, and t is 23, since 56 is greater than 23. This if condition would not hold. So I would go into my next else if condition, which says that in case my amid value comes out to be greater than my target value, which is represented here, in the last if else condition, I would update my end pointer to mid minus one. Now, you would have seen my ending pointer was here. Now, what the algorithm tells me to do is that I should update my ending pointer to mid minus one, which is I should bring my ending pointer here since this is mid. So mid minus one would be here. So this is what is happening in the next step. In the next step, my s pointer remains constant, whereas my e pointer, my ending pointer, has shifted and come here on 38. So in this step, I would

be left with two elements. In this case, my start element would be this one and my ending index would be this one. I would then repeat the procedure again and find the mid index. In this case, my mid index would come out to be the same as the start index, which is this one. Now, I go into the first if condition and see if my target value equals to equals to amid. Since my mid was this and amid equals to 23, it matches with the target value of 23. So this if condition has been successful. So on the success of a condition, what I do I return mid. That is, I return the index of this particular element since it matches with our target value. So this is how I keep on checking in each step how my mid index value compares with the target value I want to find. And based on that, I update either my start pointer or I update my end pointer. Or if those two values match, then I return the index of the matched element.

Video Recap

Binary search algorithm helps to find if a specific element exists in a sorted array.

The function 'binary' takes two inputs: array 'a' and target element 't'.
The variables n, start, and end are defined where n denotes array length, start denotes starting index, and end denotes ending index of the array.
The middle element is found by calculating the mid index as (start + end) / 2.
There are three if-else conditions to compare the target value with the middle value.
If the target value is greater than the middle value, then the start pointer is updated to mid + 1.
If the target value is less than the middle value, then the end pointer is updated to mid - 1.
This process is repeated until the target element is found or the search space is exhausted.
If the target element is found, then the index of the element is returned.
Binary search works efficiently with a sorted array.

Learn how binary search works with this simple pseudocode and example. The function 'binary' takes two inputs - the array and the element to find. The algorithm compares the target value with the middle value and updates the start or end pointers accordingly. Repeat until the target element is found or the search space is exhausted. This efficient algorithm returns the index of the matched element. Use binary search with a sorted array to find elements quickly.

We know that all is not explained till now. There has not been any discussion on why the condition start<= end is being used in the pseudocode. You shall be provided with an explanation for the same in the next video.

$$/$$

Great! If you have understood the pseudocode well, the Java implementation discussed in the video below shall be a cake-walk for you. You can download the Java file given below for Binary Search Code.

$$/$$

Though in the video and at many other places in this course, Aishwarya has used (start + end)/2 to calculate the value of the middle index, and it works fine in most of the cases as well, we still recommend you to use either of the following:

start + ((end - start) / 2);

(The reason for the same can be found here.)

start + (end - start)/2

(The reason for the same can be found here.)

Great! You now know how to write a Java code for the binary search algorithm. So, let’s move to the next video, where Rachit will find the jack of spades in the same set of 11 cards. Let’s see how many steps he takes using binary search.

$$/$$

So, it took Rachit four steps using binary search, while it took 11 steps using linear search. This clearly illustrates the fact that binary search is much more efficient than linear search.