>> [MUSIC PLAYING]
DOUG LLOYD: Linear
search is an algorithm we
can use to find an element in an array.
An algorithm recall
is a step-by-step set
of instructions for completing a task.
>> The linear search
algorithm works as follows.
Iterate across the array from left to
right, looking for a specified element.
>> In pseudocode, which is a more
distilled version of this sentence,
if the first element is what
you're looking for, you can stop.
Otherwise, move to the next element and
keep going over and over until you find
the element, or you don't.
So we can use the linear
search algorithm, for example,
to find the target value
nine in this array.
Well we start at the beginning.
If it's what we're
looking for, we can stop.
It's not, we're not looking for 11.
So otherwise, move to the next element.
>> So we look at 23.
Is 23 what we're looking for?
Well no, so we move on to the next
element, and the next element,
and we keep going through
this process over and over
and over, until we land
on a situation like this.
>> Nine is what we're looking for,
and this element of the array
is, it's value is nine.
And so we found what we're
looking for, and we can stop.
The linear search has
completed, successfully.
>> But what about if we're looking for
an element that's not in our array.
Does linear search still work?
Well sure.
So we repeat this process
starting at the first element.
If it's what we're
looking for, we can stop.
It's not.
Otherwise, we move to the next element.
>> But we can keep repeating this process,
examining each element in turn,
hoping that we find the number 50.
But we won't know if
we've found the number 50
or if we didn't, until we've stepped
over every single element of the array.
>> Only once we've done
that and come up short,
can we conclude that
50 is not in the array.
And so the linear search
algorithm, well it failed, per se.
But not in the sense that it
was unsuccessful in doing what
we asked it to do.
>> It was unsuccessful in as
much as it didn't find 50,
but 50 wasn't in the array.
But we have exhaustively searched
through every single element
and so, while we didn't find
anything, linear search still
succeeds even if the
element is not in the array.
>> So what's the worst case
scenario with linear search?
Well we have to look through
every single element,
either because the target element
is the last element of the array,
or the element we're looking for doesn't
actually exist in the array at all.
What's the best case scenario?
Well we might find the
element immediately.
And how many elements
do we then have to look
at in the best case,
if we're looking for it
and we find it at the very beginning?
We can stop immediately.
>> What does this say about the
complexity of linear search?
Well in the worst case, we have
to look at every single element.
And so it runs in O of
n, in the worst case.
>> In the best case, we're gonna
find the element immediately.
And so runs in omega of 1.
>> I'm Doug Lloyd.
This is CS50.
