Tip:
Highlight text to annotate it
X
[Linear Search]
[Patrick Schmid, Harvard University]
[This Is CS50.] [CS50.TV]
Searching is something that you probably do more often than you think.
Obviously, every time you open up a web browser
and search for a web page--
or search for your friends on your favorite social networking site--
you are searching.
But that's just a small part of the searching that you do on a daily basis.
When you want to find that one blue shirt in the closet,
or that perfect red blouse for the occasion,
you're searching.
When you go to a store that you've never been to before,
and you're looking for the broccoli in the produce aisle,
you're searching.
What you may have started to notice
is that depending on what you're looking for
or how the items are organized when you're looking for them,
it has an effect on how you search.
For example, if your shirts are hanging in the closet,
you can probably just pick it out without much searching.
If you're assuming you have to walk down the aisle
to get the broccoli, you probably have to look at all other vegetables
before you find that broccoli.
Linear Search is an example of one such searching method--or algorithm.
As the name implies,
this method searches for an item in a linear fashion, one after the other.
So, when you're looking at the results from your favorite search engine
and you read down the list of results,
you are using linear search.
Okay. Let's look at an example.
Say we have a list of numbers--2, 4, 0, 5, 3, 7, 8, and 1--
and we're looking for the number 0.
Obviously, you can just see that the 0 is in the third position.
But, a computer program isn't that fortunate.
It can only "see" one number at a time.
So, starting at the beginning of the list,
it only "sees" the 2.
The program then checks--is 2 equal to 0?
Obviously not. So it goes on to the next number, 4.
Does 4 equal 0? Nope.
The next one, 0. Ah! Zero is equal to 0.
There we have it! It's in the third position.
Okay. Let's look at some pseudocode.
It's only a couple of lines long, but let's look at it one line at a time.
First, let's define the function--and we're going to call it linear search--
and it takes two arguments--key and array.
The key is that value that we're looking for,
so in the previous example, that was the zero.
An array is a list of numbers
that has all the values that we're going to search.
So, what we want to do is we want to look at--
from all positions, so starting at the very beginning of the array
til the very end of the array--so the length of the array--
look at every single position and check each one.
So that's what that "for" loop is doing.
And at each position, we're going to say
"Is that value at that current position equal to the key that we're looking for?"
So--in the previous example again, key was 0--
so we are saying "Is the array at position i equal to 0?"
If it is, we're going to return 'i' because that's the current position we're at.
So, in the previous example,
that was the third position.
If we've gone through the entire array
and we haven't found anything--
so let's say we were looking for the number 500
which clearly wasn't in that example--
we have to return something,
and we're going to return -1.
And we're just returning -1 because that's a position
that does not exist in the array.
And so that means when you get it back from a function
it says "Hmm, okay. I guess I didn't find anything.
So that 500 never was there."
The nice thing about linear search is that
it'll work on any list of items,
regardless of how the items are ordered.
It doesn't matter where the broccoli is in the produce aisle.
As long as you walk down the aisle from the beginning to the end,
you're bound to find it,
assuming the store hasn't run out of broccoli, of course.
But its greatest strength is also its greatest weakness.
Say you have a list of two hundred numbers
that are sorted from 1 to 200.
If you're looking for the number 198,
you have to search almost the entire list of numbers
before you find the one you're looking for.
There must be a better way!
Rest assured, there is.
But, that's a topic for another video.
Also, don't fret!
Just because linear search isn't the best solution in all situations,
it doesn't mean that it doesn't come in handy.
Otherwise, how would you find that broccoli in the produce aisle?
My name is Patrick Schmid, and this is CS50.
[CS50.TV]