Pseudo Code Binary Search

[00:00:00]
>> So this is binary search, greatest algorithm ever. So now that we've kind of written it on a whiteboard, we could implement it. But first, what I'm going to do is, I'm going to probably do it a little bit nicer this time. Let's try to do it and do it in a sense that makes it easier to translate to code, all right?

[00:00:16]
So let's think about it more in kind of a pseudocode type sense. We know we're gonna have the array, we know we're gonna look on either side, we know we're gonna do this. So let's do this a little bit better. So if we think about it, we could have a function that has search, that takes in an array, and maybe it has a lo and it has a hi, right?

[00:00:34]
This is the space in which you need to look into, right? That makes sense. And so, what we could do is, we could do a loop until some sort of condition happens, right? What would be a good condition that would happen? Does anyone have an idea?
>> Comparing to the low rhythm.

[00:00:51]
>> Yeah, exactly, when the low and the high effectively become each other, we're done, right? Because that means we've halved their space to the point where we can no longer halve our space. So that's a good thing to kinda remember, conditions always. But let's just kind of walk over this in a more practical sense.

[00:01:08]
So if we start here, what we need to do is we need to go from our low to our high and find the middle point. All right, so that's pretty easy. Let's just write some pseudocode, all right. Midpoint, simply is going to be lo+(hi-lo) divided by 2 and the flow of that operation, right?

[00:01:30]
That makes sense, we're getting the middle point. Because if we're starting from a middle position, we're gonna need to make sure that we adjust where we're at, that's why we do the low plus, and then we need to just look at a specific space. So we get the midpoint with the offset, awesome, we're good to go.

[00:01:45]
So then we need the value at that point, right? So we can do something like array midpoint, right? So we now have the value. All right, awesome, so what do we do in our three conditions? Does anyone know what the three conditions are? Condition one, Value is the thing we're looking for, right?

[00:02:03]
I forgot to put this in here. We'll just call it n for needle. There we go. If value equals needle, well, we can return true, in this case. We'll just make it simple, right? We're gonna just return true. We found the value, it does exist, here we go.

[00:02:19]
We could return the index if we wanted to, which would just simply be that right there, doesn't matter. All right, or we have our value is actually larger than the midpoint, right? So, what does that mean? We're looking at this position right here. What that means is our value is larger than this position.

[00:02:40]
Which means that it's larger than everything on this side. Which means we simply need to only look on this side, right? That makes sense. So we will simply have to do something, we need to do something to be able to do that. And the easiest way to do it is just adjust our lo, right?

[00:02:57]
Our lo should equal the midpoint plus 1. We don't need to consider the midpoint cuz we already know it's not the right value. So we just adjust our low end and put it right in front of where the midpoint is. Else, we can say, hi, we now need the else condition is that our value is actually lower than the current value, which means that we need to go on to the lower side.

[00:03:19]
So our hi needs to equal our midpoint. Now, remember, I usually, whenever I do things, I for the most part, will do something that looks like lo is always inclusive, hi is always exclusive. Always have these things in your head or else this +1 right here is gonna just eat your lunch.

[00:03:38]
You're always going to be off by 1, things are always gonna break down. Always come in with a plan or else it destroys you. And that's pretty much the extent of the algorithm. Now all we need to do is just effectively come up with our exit condition of this loop and we've done it, right?

[00:03:55]
Right, so our exit condition can be as simple as this, let's use the lord's loop, a do while loop. I just like to throw those in there cuz they're funny. Anyways, so there we go, do while lo, oopsies, lo is less than hi, right? We just keep on going until we finally come to a crossing point.

[00:04:16]
Cuz once we come to a crossing point, we're done. They're gonna always keep getting closer to each other right here. So we'll know that will eventually happen. And if we get here, we can just simply return false, doesn't exist. If you're returning the index, you could do a sentinel value of -1, that's what it's called, it's called a sentinel value, pretty fun.

[00:04:33]
I don't know why I always think about the matrix or sentinels, I don't know why that makes that association, but it just does. So there you go. That is effectively the entirety of a pseudocode version of binary search. Does this all make sense? Normally why, we got one question.

[00:04:49]
>> Yeah, shouldn't it be less than equal to high?
>> We don't wanna do less than or equal to. Cuz if you think about it, you see, this is the classic, this is an off by 1, this is another off by 1. What does this mean? It means that low is included but high should not be included.

[00:05:04]
So if we include 1, but we should exclude 1, what does that mean? Means we shouldn't use 1, right? Cuz it means that our pointers are actually behind each other, is what that really, really means. In other words, if we're at some position, we'll just call this thing xi.

[00:05:22]
We have a pointer that says, hey, I want to start here and then our end pointing says, hey, don't cross this line. So it's fundamentally in a broken state. And so we don't want to look there. So that's how I always think of it, is I just have to have my off by 1's really strong, or else I goof it up.

[00:05:39]
All right, now that we've done that, let's, or actually is there any questions?
>> This is all under the assumption that the array is sorted, correct?
>> It's all under the assumption that the array's sorted, you can never do this on a non-sorted array. The reason, again, is when you come back up to this part.

[00:05:58]
When you come to these two conditions, it has to be able to make the assumption that if I am larger than the current element, then the rest of that side of the array, the left-hand side is all lower than me. I know that for a fact. Everything over here could be larger or lower than me, I don't know that, yet.

[00:06:15]
But it reduces your search space by half each time cuz you can make that single value statement.