Binary Search Practice

[00:00:00]
>> All right, let's hop into the CodeSandbox here, it's under Search. So search.test.js. I have two for you here to try. You can do a linear search, if you want to, which is just really you're gonna loop over and say, is this it, is this it, is this it, right?

[00:00:30]
Feel free to skip that one, I'm actually less interested in you doing that one. I'm more interested in you doing the binary search here. So here we have a binary search. Here, right? And we're looking for someone here in this, right? In this case, we're looking for 23.

[00:01:00]
Study them in there it is looking for, right? Okay? So I'm gonna call it binary search with 23, right? And what I want you to do here on this unit test is, I want you to write a binary search where you look for ID 23 and you return back to me this particular object.

[00:01:26]
And then if you have extra time, go ahead and give the linear search a shot too. All right, let's do some searching, soul searching. I'm gonna change LinearSearch to be called soul search instead, just kidding. Let's just do this linear search really quick. It's just one really simple for loop here, let i = 0, and there's a just a trillion different ways you could do this.

[00:01:59]
I'm gonna do with a for loop because we've been doing that the whole time, but you absolutely could have done a reduce a filter for each. Something like that, any one of those would have been fine. if (id === array[i].id), then return array[i]. Otherwise, you can return null, you can return undefined.

[00:02:36]
I'm gonna do return void 0, which is undefined, right? Okay, so here we do that, remove the skip. Take a look at the tests and run them again. We should here on search, so far so good, nothing broken, cool. Binary search here, let's do, let min = 0, let max = array.length-1.

[00:03:16]
Again, array here, by definition, must be a sorted array or binary search is not going to work. Whereas, linear search here it can be done on any array, sorted or not, okay? Let index, let element. Okay, and then you just say while(min <= max), index is going to be equal to Math.floor.

[00:03:55]
And here we're gonna say (min + max) divided by 2. So again, we're kinda just moving halfway between these. That's what this index is, the Math.floor(( min + max) divided by 2) equals. And then we're gonna say element at that particular array is equal to array[index]. So this is whatever the element is here.

[00:04:26]
So we're gonna say here if element.id is greater than id. Then min is going to be equal to index + 1. So that we're setting the minimum index to be one greater than the elements that we were just looking for, right? Also the element that we were just looking at rather, not looking for.

[00:05:00]
Else if element.id is greater than id, then max is going to be equal to index- 1, as you might imagine. So if the item that we're looking at is greater than the thing that we're looking for, then we're going to move the max one underneath it. So if it's not less than, and it's not greater than, then that means by definition, it's that, right?

[00:05:31]
We found the thing, in which case we say return element. Okay, so if it's in the array, this logic will find it. If this while loop breaks, which means that the max and the min overlap, that means we have looked at the entire array and we did not find it.

[00:05:54]
In which case you can return null, return void 0. I like undefined because it just means that that's not there, right? You technically could have something that's null in the array, but again, we're splitting hairs. It depends on the semantics you want to assign to undefined or null, but I think actually undefined a better answer, so let's just go with that.

[00:06:17]
Okay, so that should do that. Let's go ahead and remove this and see if our tests pass. And looking down here at search.test.js, looks like it works.