Binary Search

[00:00:00]
>> I imagine many of you kind of like conceptually already understand this, even if you haven't put a name to necessarily this algorithm. But it's useful for you to just kind of put a name to it right at once make sure you understand it. The act of searching is kind of similar to sorting and the fact that you are comparing numbers one to each other.

[00:00:20]
But in this particular case, we're not trying to get all the numbers in one particular order we're actually just trying to find one particular element in the array. If you're running a search on a array that's not sorted, the only kind of search you can really do is linear right which is you just write a for loop or a while loop and say like is this it?

[00:00:40]
Is this it? Is this it? And you just kinda go pick for that that just checks every single element in the array. However, if you have an array that's already sorted, you can use binary search. And I imagine if you're old enough to remember phonebooks, [LAUGH] Which may not be everyone that's watching this video.

[00:01:02]
The way that you search in a phonebook if you're looking for I don't know, hold in the phonebook, you open it to the middle, you're gonna land on like M or N. And then you're gonna split the difference and go halfway between M and N, right? And then you're just gonna keep going half and half and a half until eventually learn on the Hs than the HOs and the HLs, right and then eventually we'll find holes right.

[00:01:23]
So this algorithm of splitting the array in half and then half and then half and in half until eventually you land on the exact correct element it's called the binary search, right? So, imagine we have this array here, again, binary search works only if it is sorted, right, and we're looking for 12.

[00:01:45]
So what you do you always you just start in the middle, right? So the middle is 19, you say is 19 equal to 12? No, it's smaller and then you go to the left and you split the difference there. So you look in the middle of the smaller half.

[00:02:00]
So between 19 and 0, that middle is going to be ten, right? You ask this ten equal to 12? The answer no it's not. So you go larger, right? And you go right and you look in the middle of the larger half, which is between, in this case just between 10 and 12, right?

[00:02:19]
And then you just look there, which is going to be 12. And then you ask as well be equals to 12, yes, you found the element that makes sense. Just keeps cutting the array in half until eventually you find that the item that you're looking for. One of the questions you might ask is like, if it's of length 3, do I go to the smaller side or the larger side?

[00:02:44]
Doesn't matter, just pick 1. I think in this particular case I went to the smaller side, which is why we looked at 10 first instead of 12. Any questions about the algorithm of binary search? Is this best done recursively? No, I would say this is much better done with a loop than it is.

[00:03:07]
Yeah, I guess you could totally do this with recursively. I probably would do this with had loop. Let me just make sure that I'm not telling you lies here. Search. Yep, either way though, I mean, honestly, binary search, even on extremely large arrays. Is really effective. So you probably would be fine to do it in recursive ways as well, but my solution is iterative.

[00:03:54]
What is the O of this? Well, we're not looking at every element in the array, right? So it's not n it's gonna be less than n because we're just starting in the middle and then we're going to the side that we need to. So we're not looking at every element in the array.

[00:04:11]
So less than n, we do have to look at some elements in the array. And it also we get economies of scale if we have extremely large datasets. So that puts us at login, right? So binary search as an algorithm is time complexity, login. And if you don't create any additional data in the process, so it's constant space.