Implementing Binary Search

[00:00:00]
>> And so since we did that, let's do of course the greatest thing ever. Let's go over to our coding machine, go back to day 1, and look for, what is it, binary search. Yeah, look at that. So, now we can implement binary search right here right now.

[00:00:15]
So, notice that we're given a haystack and a needle, again. So, as always, let's start off of course, with the lowest loop, a do while loop. You don't have to use this. And let's create a let lo=0, put this, and a hi, I'll just keep them the same naming convention as my pseudocode.

[00:00:36]
A hi=haystack.length, awesome. So now again, we need to grab the midpoint. So, let's go const m for midpoint, math.floor. And we'll do lo+ hi- l divide by 2. I put that little note, don't forget to divide by 2 because when I program this took me like three minutes to realize I had a bug cuz I forgot to divide by 2.

[00:01:02]
Don't forget to divide by 2, it's very, very important. const value, of course gonna be haystack m. You're gonna see this a lot in algorithms that they use single letter variables to denote everything. I'm just kind of following the pseudocode style so that way it's a fairly easy direct translation from this into here.

[00:01:21]
Normally, program with good names but in this case we're just gonna keep it like that, all right? So if value is equivalent to the needle, we have found it ,right? I'll take that down here and do a little false, there we go. And we need to come up with a nice condition right here as of course is while lo is less than hi.

[00:01:42]
All right, so our three conditions of course are gonna be when value is equivalent to needle, we found it, awesome, let's return true. But if value is greater than needle, that means anything to the right hand side, is gonna be greater than me. I'm already greater than at this current point, so the rest of the right hand side, is gonna be greater than, so I want to reduce the high side, to this point and exclude the midpoint.

[00:02:09]
So, hi equals midpoint, cuz remember, hi as exclusive, lo is inclusive, awesome. Let's just cut and paste that. So, we can reverse the condition or we can just do an else statement. We'll just do an else statement to make it simple. Now remember, what this means now is that our value is less than our needle.

[00:02:30]
Which means that we need search on the higher side, right? Our needle is greater than our value, that means if we're gonna exist in this array, we're somewhere in the greater side region. So, lo=m+1, cuz again, drop the midpoint. You don't want to look at the midpoint again, it would be silly if you looked at the midpoint again.

[00:02:52]
Just having these conditions on your brain long as I've done this all correct, we should be able to see this thing. Go first try it. Let me just make sure that I've actually done this correct ,mpx just binary. That is not how you spell binary, is it? Come on, okay, well we have two operations in there.

[00:03:11]
Don't look at the second one compare binary tree, you're not actually supposed to see that quite yet. So, let's pretend the man behind the curtain doesn't exist but yeah, binary search actually worked, first try. All right, there we go. So I don't think I put this in my presentation, but one of my first interviews at Google, they made me code binary search in Google Docs.

[00:03:31]
It was terrible, and I had plus 1 minus 1 issues all over the place. I didn't come into it with a really clean idea of exactly what needed to happen. This algorithm is actually pretty simple, right? Like, that's not a hard amount of code to do it. It's really only what, seven lines of actual code, the rest is all spacing or it's like nothing, right?

[00:03:54]
Initialization spacing, so it's actually a pretty simple piece of code, it's just being able to focus on this and do this correctly. Do we have any questions?
>> Just a quick thing in the repo, I couldn't see the day 1 folder. Do we have it there? I just see the test folder in the repo.

[00:04:10]
>> So it is. So, what editor are you? So the question was I can't see the day 1 folder. What's happening? What editor are using?
>> I'm using Visual Studio code.
>> Okay, so code, is it hiding, get ignored folders?
>> I'm not sure if what it is that they're integrating.

[00:04:26]
>> It's a get ignore it so that way you can generate a lot of them and you don't have a huge amount of uncommitted changes. So, if you're using visual code, I don't use code. I didn't know that but if it hides, ignored folders, you're not gonna be able to see day 1.