Four Semesters of Computer Science in 5 Hours, Part 2 Searching for an Element in an Array Solution

Transcript from the "Searching for an Element in an Array Solution" Lesson

[00:00:00]
>> Brian Holt: Okay, linear search, for let i = 0, i is less than array.length, i++, if id triple equals array of i.id, then return array of i. Otherwise, whatever, it doesn't matter. I have in my notes return void 0, which is is just a way of saying return undefined.

[00:00:41] It would also be exactly the same if you just didn't do that. But sometimes it's good to be explicit, it depends on what you want to do. Binary search. Function binarySearch. So what I'm going to do here is I'm going to say, let min = 0, let max = array.length- 1, right?

[00:01:04] So that's the end of the array, so that's the currently the section that I'm searching on, then let index, and let element. These are the kind of the two things that I'm looking at any given time. Now, I'm just gonna do a while loop. I'm gonna say while min less than or equal to max, because as soon as that's no longer true, then I've covered enough of the array to assuredly say it's not in the array.

[00:01:40] So I'm gonna say if element, sorry, I have to do this first, so I'm gonna say index = (Math.floor, min + max)/2. The reason why I do Math.floor is because this could be 0.5, right? So 9 divided by 2 is gonna be 4.5, you wanted to look at 4, right?

[00:02:00] It doesn't matter if you go up or down I don't think, but we'll be going down. Element which is the current element that we're looking at is array index. So if element.id is less than id, min = index + 1
>> Brian Holt: Right, because we're gonna shorten our search to where we currently are, else if element.id is greater than id.

[00:02:39] Then we're gonna say max = index- 1. Okay, that's,
>> Brian Holt: This is, just gonna make this stop auto updating cuz we're in the while loop and it's messing me up. Okay, index- 1, right, cuz we're then gonna move the max back. Else return element because if neither one of those is true then we've reached the element that we're looking for and we return the element.

[00:03:17] Otherwise, you return void or whatever you want to do. So now if we try and run it.
>> Brian Holt: Passed our test. So that's a basic binary search right there. Just kind of moving the sliders until eventually you either land on the element or you've run out of space to move the sliders and you're done.

[00:03:35] The sliders being min and max, right?