1
00:00:00,000 --> 00:00:02,892
>> [MUSIC PLAYING]

2
00:00:02,892 --> 00:00:05,347

3
00:00:05,347 --> 00:00:07,180
DOUG LLOYD: Linear
search is an algorithm we

4
00:00:07,180 --> 00:00:09,840
can use to find an element in an array.

5
00:00:09,840 --> 00:00:11,990
An algorithm recall
is a step-by-step set

6
00:00:11,990 --> 00:00:15,030
of instructions for completing a task.

7
00:00:15,030 --> 00:00:17,480
>> The linear search
algorithm works as follows.

8
00:00:17,480 --> 00:00:22,200
Iterate across the array from left to
right, looking for a specified element.

9
00:00:22,200 --> 00:00:26,380
>> In pseudocode, which is a more
distilled version of this sentence,

10
00:00:26,380 --> 00:00:29,840
if the first element is what
you're looking for, you can stop.

11
00:00:29,840 --> 00:00:33,930
Otherwise, move to the next element and
keep going over and over until you find

12
00:00:33,930 --> 00:00:36,389
the element, or you don't.

13
00:00:36,389 --> 00:00:38,680
So we can use the linear
search algorithm, for example,

14
00:00:38,680 --> 00:00:42,330
to find the target value
nine in this array.

15
00:00:42,330 --> 00:00:43,870
Well we start at the beginning.

16
00:00:43,870 --> 00:00:45,970
If it's what we're
looking for, we can stop.

17
00:00:45,970 --> 00:00:47,890
It's not, we're not looking for 11.

18
00:00:47,890 --> 00:00:50,220
So otherwise, move to the next element.

19
00:00:50,220 --> 00:00:51,510
>> So we look at 23.

20
00:00:51,510 --> 00:00:52,730
Is 23 what we're looking for?

21
00:00:52,730 --> 00:00:55,614
Well no, so we move on to the next
element, and the next element,

22
00:00:55,614 --> 00:00:57,780
and we keep going through
this process over and over

23
00:00:57,780 --> 00:01:01,030
and over, until we land
on a situation like this.

24
00:01:01,030 --> 00:01:03,910
>> Nine is what we're looking for,
and this element of the array

25
00:01:03,910 --> 00:01:05,787
is, it's value is nine.

26
00:01:05,787 --> 00:01:08,120
And so we found what we're
looking for, and we can stop.

27
00:01:08,120 --> 00:01:11,910
The linear search has
completed, successfully.

28
00:01:11,910 --> 00:01:15,370
>> But what about if we're looking for
an element that's not in our array.

29
00:01:15,370 --> 00:01:17,040
Does linear search still work?

30
00:01:17,040 --> 00:01:17,540
Well sure.

31
00:01:17,540 --> 00:01:19,947
So we repeat this process
starting at the first element.

32
00:01:19,947 --> 00:01:21,780
If it's what we're
looking for, we can stop.

33
00:01:21,780 --> 00:01:22,800
It's not.

34
00:01:22,800 --> 00:01:25,020
Otherwise, we move to the next element.

35
00:01:25,020 --> 00:01:29,050
>> But we can keep repeating this process,
examining each element in turn,

36
00:01:29,050 --> 00:01:31,720
hoping that we find the number 50.

37
00:01:31,720 --> 00:01:33,750
But we won't know if
we've found the number 50

38
00:01:33,750 --> 00:01:38,290
or if we didn't, until we've stepped
over every single element of the array.

39
00:01:38,290 --> 00:01:40,440
>> Only once we've done
that and come up short,

40
00:01:40,440 --> 00:01:43,040
can we conclude that
50 is not in the array.

41
00:01:43,040 --> 00:01:46,410
And so the linear search
algorithm, well it failed, per se.

42
00:01:46,410 --> 00:01:49,181
But not in the sense that it
was unsuccessful in doing what

43
00:01:49,181 --> 00:01:49,930
we asked it to do.

44
00:01:49,930 --> 00:01:52,390
>> It was unsuccessful in as
much as it didn't find 50,

45
00:01:52,390 --> 00:01:54,070
but 50 wasn't in the array.

46
00:01:54,070 --> 00:01:57,310
But we have exhaustively searched
through every single element

47
00:01:57,310 --> 00:02:00,550
and so, while we didn't find
anything, linear search still

48
00:02:00,550 --> 00:02:05,230
succeeds even if the
element is not in the array.

49
00:02:05,230 --> 00:02:07,507
>> So what's the worst case
scenario with linear search?

50
00:02:07,507 --> 00:02:09,590
Well we have to look through
every single element,

51
00:02:09,590 --> 00:02:14,590
either because the target element
is the last element of the array,

52
00:02:14,590 --> 00:02:18,510
or the element we're looking for doesn't
actually exist in the array at all.

53
00:02:18,510 --> 00:02:19,760
What's the best case scenario?

54
00:02:19,760 --> 00:02:22,430
Well we might find the
element immediately.

55
00:02:22,430 --> 00:02:24,360
And how many elements
do we then have to look

56
00:02:24,360 --> 00:02:26,859
at in the best case,
if we're looking for it

57
00:02:26,859 --> 00:02:28,400
and we find it at the very beginning?

58
00:02:28,400 --> 00:02:29,850
We can stop immediately.

59
00:02:29,850 --> 00:02:32,984
>> What does this say about the
complexity of linear search?

60
00:02:32,984 --> 00:02:35,650
Well in the worst case, we have
to look at every single element.

61
00:02:35,650 --> 00:02:38,930
And so it runs in O of
n, in the worst case.

62
00:02:38,930 --> 00:02:41,540
>> In the best case, we're gonna
find the element immediately.

63
00:02:41,540 --> 00:02:44,750
And so runs in omega of 1.

64
00:02:44,750 --> 00:02:45,780
>> I'm Doug Lloyd.

65
00:02:45,780 --> 00:02:48,020
This is CS50.

66
00:02:48,020 --> 00:02:49,876