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

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

[00:00:03]
>> Brain Holt: Searching for elements in an array. What we're gonna do here is we're gonna have some sort of item that we're looking for in some group, some array, right? There's kind of two strategies that we can look at doing this. The first is literally a while loop where you're going through and checking is it this item, is it this item, is it this item, is it this item?

[00:00:24] Eventually, that question is gonna either be yes or no. If it's never yes, then you never found it. If it is yes, then you just reach for that item. This is called a linear search, the Big O of this would be N, right? Because potentially you could go through every item and it would not be there or it could be the first item.

[00:00:42] So it has a really random or full distribution of best case and worse case. If there is some sort of order to the array, then you can do something called binary search which is log n which means it's much, much more efficient than just n. So what you do is you're gonna do it more or less like you do a phone book, right?

[00:01:04] You're gonna open the middle and you'll say, is it n, right, or is it n? And then you're gonna say no and so, you're gonna start bifurcating it, or dividing it in half until eventually, you're gonna land on the item that you were looking for. All right, so I kind of diagrammed it out here.

[00:01:20] If you are searching for 12, you are gonna start in the middle and say is it 19? No, is it ten? No, is it 12? Yes, right, so you just kind of keep going back. Just adding half or subtracting half until eventually you land on the item that you are looking for.

[00:01:38]
>> Brain Holt: So let's just go ahead and do an exercise real quick. And give you an array, the first one, the linear search array, it's gonna be in no order or whatsoever. And I want you to just go through and find the item that you're looking for and return it.

[00:01:54]
>> Brain Holt: Excuse me, for the second one for binary search, you're going to go through and it is an ordered list and you're gonna do a binary search to find which item that you're looking for. So I'll give you a second to do that, the first one takes about 5 lines of code.

[00:02:14] The second one takes maybe about 15 lines of code to accomplish.