Welcome back.
Let's now go ahead and implement the binary search.
As we discussed in the previous video.
First we'll implement the iterative version of the binary search.
So for this let's call our function binary search.
Iterative.
All right.
Now this function is going to take in the array of integers which is numb's and the target value.
Now, once we are inside the function, let's have two pointers left and right.
So left is going to be equal to zero, which is the left most index of the array which is given to us.
And right is going to be the right most index which is numb's dot length minus one.
Now we're going to have a while loop, which will go on as long as left is less than or equal to right,
so that we can keep searching for the number which is given to us.
Now we will need a pointer middle.
Let me just initialize it over here so that we don't keep initializing it at every loop.
All right.
So inside this we are going to calculate middle.
And middle is going to be math dot floor.
Left plus right divided by two.
Now we can do ceiling also.
But over here we're just doing floor.
Now once we find the middle index you're going to check if the number at that particular index is equal
to the target which is given to us or not.
So let's do that over here.
So if target is equal to numb's at middle in that case we have found the integer which we are searching
for.
And we can just return that particular index which is middle.
Now if this is not the case, we will check whether target is less than the value at the middle index.
So if target less than numb's at middle, if this is the case, then we'll have to search only on the
left part from the middle index.
So we're going to move the right index to middle minus one.
So right is going to be equal to middle minus one.
Now if this is not the case then we will move left to middle plus one right.
Because if this is not the case that means that target is greater than num said middle right.
So if that is the case then we will move our left pointer to middle plus one, because we only want
to search in the right part of the middle value.
All right.
So this will keep looping as long as left is less than equal to right.
And when we are done with this when we come out of this while loop, if we have not returned anything
so far, that means that the target value is not there in the Nums array, so we can just return minus
one in that case.
All right.
So we're done with our function.
Now let's go ahead and test our function by calling it.
So I'm just saying binary search iterative.
Now we will need to pass the array.
So let's say 12345 is the array which you're passing in.
And let's say we are searching for the value five.
Now let's go ahead and call the function and see what's happening.
So you can see we are getting the value for which is correct.
Right.
So five is at index 40123 and four.
So this is at index four.
So yes that's working.
Now let's just call it for value one.
Let's say the target value which you're searching for is one.
So we are getting the index zero which is this index over here.
So yes that's also working.
Now what if we pass a value which is clearly not there in our array.
So we're getting minus one.
So that means that this integer over here ten is not there in the array which is given to us.
All right.
So this function is working.
Now let's take an example and just let's walk through the code.
All right.
So let's take this same example which we have over here.
So we have the values one, two, three, four, five and the target value is ten.
So that's passed to the function over here.
Binary search iterative.
Now initially left is pointing at zero.
So we have left pointing to index zero.
And then we have right pointing to numb's dot length minus one.
So over here the length is five.
So five minus one is four.
So this is index four.
So right is pointing over here.
And then we come inside the while loop.
Now zero.
This is zero right.
Zero is less than four.
So yes this is truthy.
So we come inside the while loop.
Now middle is calculated as zero plus four divided by two.
And then we are floating it.
So we get the value of middle as two.
And then we are going to find check the compare the value of target and numb's at middle.
So this is zero one and two.
So this is index two right.
So this is where middle is pointing to at this moment.
Now we can see that the target is ten.
So ten is not equal to three.
So we don't go inside over here.
Then we come to this line of the code and we are checking whether ten is less than three.
No that's not the case.
Right.
So we come over here and we move left to middle plus one.
So let me just change the color.
So we move left this one to middle plus one which is over here right.
So index three.
So left is pointing to index three.
And then again we come over here we see that three is less than four.
So we come inside the while loop.
And again we calculate middle as three plus four divided by two which is 3.5.
And then we are just flooring it.
So we get the value of middle as three.
So middle is also pointing to index three at this point.
All right.
So let me just rub these two.
So middle is also pointing to index three and left is also pointing to index three.
Now we are going to check the target value and compare it with the value at middle index.
So the target value is ten and the value at the middle index is four.
Right.
So four is not equal to ten.
So we don't go inside over here.
Then we come and check whether for ten is less than four.
That's not the case.
So we come over here right.
So we come again to this part and we change left and we make it middle plus one.
Right.
So this over here from three it's pointing to four at this moment.
So left is also pointing at four.
Right is also pointing at four.
Now we come again over here we see that four less than or equal to four is truthy.
So we come inside the while loop and we recalculate the middle value.
At this point.
Middle is four plus four by two which is four itself.
So middle also is at four.
And we are checking whether five.
The value at index four is five.
Right.
We are checking whether five is equal to ten.
That's not the case.
So we don't go inside over here.
Then we come over here.
We check whether five is less than ten.
And no whether ten is less than five.
Right.
Whether the target is ten.
So is ten less than five.
No that's not the case.
So again we come over here and we say that left is middle plus one.
So left becomes five.
So right at this moment is four.
And left is pointing to index five.
Again we come over here and we check whether five less than or equal to four.
That's false.
So we come out and then we're just going to return minus one.
So that is how the code works.
In the case where a value is passed which is not there in our array.
And similarly if it was there then we would have identified it over here right at some point the the
middle pointer would be pointing to that particular value.
Then we would have found that target is equal to numb's at middle.
And then we would have just returned the index where the value was.
The target value was equal to the value at that particular index of the array.
All right.
So this is how the iterative version of the binary search works.
Now let's go ahead and code the recursive version of the binary search.
And again what's the time and space complexity over here.
Let's take a quick look at that.
Now clearly the space complexity is equal to O of one or constant space, right?
Because we are not using any scaling space, we are not creating a new array or a hash map, etc..
So the space complexity over here is O of one or constant space.
And and again you can notice that this is the iterative version.
So that's why the space complexity is O of one we don't have.
Again we are not using space on the recursive stack as well.
Now what about the time complexity?
Now the time complexity of this solution is going to be O of log n.
Why is that so?
Because at every step we are eliminating half of the remaining values.
And this type of a relation is log n time complexity.
Right.
Again notice log of four is equal to two and log of eight is equal to three.
So this is also another way in which you can think about it when we are doubling the size right.
So n is the input array size.
So when we are doubling the size the number of checks is only increasing by one.
So that's again another way of looking at it.
The time complexity of this solution is O of log n, and the space complexity is O of one or constant
space.
Because this is the iterative solution, and we are not using any extra space to come up with our solution.