1
00:00:00,000 --> 00:00:09,560

2
00:00:09,560 --> 00:00:13,120
>> ZAMYLA CHAN: The first thing you might
notice about find is that we already

3
00:00:13,120 --> 00:00:14,520
have code written for us.

4
00:00:14,520 --> 00:00:16,219
This is called distribution code.

5
00:00:16,219 --> 00:00:19,060
So we're not just writing our own
code from scratch anymore.

6
00:00:19,060 --> 00:00:23,870
Rather, we're filling in the voids
in some pre-existing code.

7
00:00:23,870 --> 00:00:28,860
>> The find.c program prompts for numbers
to fill the haystack, searches the

8
00:00:28,860 --> 00:00:33,260
haystack for a user submitted needle,
and it does this by calling sort and

9
00:00:33,260 --> 00:00:36,660
search, functions defined
in helpers.c.

10
00:00:36,660 --> 00:00:38,740
So find.c is written already.

11
00:00:38,740 --> 00:00:41,840
Your job is to write helpers.

12
00:00:41,840 --> 00:00:42,940
>> So what are we doing?

13
00:00:42,940 --> 00:00:45,270
We're implementing two functions.

14
00:00:45,270 --> 00:00:50,110
Search, which returns true if a value
is found in the haystack, returning

15
00:00:50,110 --> 00:00:52,430
false if the value is
not in the haystack.

16
00:00:52,430 --> 00:00:59,060
And then we're also implementing sort,
which sorts the array called values.

17
00:00:59,060 --> 00:01:01,120
So let's tackle search.

18
00:01:01,120 --> 00:01:04,550
>> Search is currently implemented
as a linear search.

19
00:01:04,550 --> 00:01:06,620
But you can do much better than that.

20
00:01:06,620 --> 00:01:11,610
Linear search is implemented in O of n
time, which is quite slow, although it

21
00:01:11,610 --> 00:01:14,920
can search any list given to it.

22
00:01:14,920 --> 00:01:21,190
Your job is to implement binary search,
which has run time O of log n.

23
00:01:21,190 --> 00:01:22,200
That's pretty fast.

24
00:01:22,200 --> 00:01:24,240
>> But there's a stipulation.

25
00:01:24,240 --> 00:01:28,910
Binary search can only search
through pre-sorted lists.

26
00:01:28,910 --> 00:01:31,450
Why is that?

27
00:01:31,450 --> 00:01:33,690
Well, let's look at an example.

28
00:01:33,690 --> 00:01:37,350
Given an array of values, the haystack,
we're going to be looking

29
00:01:37,350 --> 00:01:41,510
for a needle, and in this
example, the integer 3.

30
00:01:41,510 --> 00:01:45,220
>> The way that binary search works is that
we compare the middle value of

31
00:01:45,220 --> 00:01:49,430
the array to the needle, much like how
we opened a phone book to the middle

32
00:01:49,430 --> 00:01:51,720
page in Week 0.

33
00:01:51,720 --> 00:01:55,710
So after comparing the middle value to
the needle, you can discard either the

34
00:01:55,710 --> 00:01:59,620
left or the right half of the array
by tightening your bounds.

35
00:01:59,620 --> 00:02:04,450
In this case, since 3, our needle, is
less than 10, the middle value, the

36
00:02:04,450 --> 00:02:07,060
right bound can decrease.

37
00:02:07,060 --> 00:02:09,470
>> But try to make your bounds
as tight as possible.

38
00:02:09,470 --> 00:02:12,690
If the middle value isn't the needle,
then you know that you don't need to

39
00:02:12,690 --> 00:02:14,070
include it in your search.

40
00:02:14,070 --> 00:02:18,390
So your right bound can tighten the
search bounds just a tiny bit more,

41
00:02:18,390 --> 00:02:22,840
and so on and so forth, until
you find your needle.

42
00:02:22,840 --> 00:02:24,580
>> So what does the pseudo
code look like?

43
00:02:24,580 --> 00:02:28,980
Well, while we're still looking through
the list and still have

44
00:02:28,980 --> 00:02:33,540
elements to look in, we take the middle
of the list and compare that

45
00:02:33,540 --> 00:02:36,020
middle value to our needle.

46
00:02:36,020 --> 00:02:38,380
If they're equal, then that means we've
found the needle, and we can

47
00:02:38,380 --> 00:02:40,160
return true.

48
00:02:40,160 --> 00:02:43,940
>> Otherwise, if the needle is less than
the middle value, then that means we

49
00:02:43,940 --> 00:02:48,350
can discard the right half and just
search the left side of the array.

50
00:02:48,350 --> 00:02:51,860
Otherwise, we'll search the
right side of the array.

51
00:02:51,860 --> 00:02:55,470
And at the end, if you don't have any
more elements left to search but you

52
00:02:55,470 --> 00:02:58,030
haven't found your needle yet,
then you return false.

53
00:02:58,030 --> 00:03:02,960
Because the needle definitely
isn't in the haystack.

54
00:03:02,960 --> 00:03:06,200
>> Now, one neat thing about this pseudo
code in binary search is that it can

55
00:03:06,200 --> 00:03:11,000
be interpreted as either an iterative
or recursive implementation.

56
00:03:11,000 --> 00:03:14,900
So it would be recursive if you called
the search function within the search

57
00:03:14,900 --> 00:03:18,400
function on either half of the array.

58
00:03:18,400 --> 00:03:20,750
We'll cover recursion a bit
later in the course.

59
00:03:20,750 --> 00:03:23,210
But do know that it is an option
if you'd like to try.

60
00:03:23,210 --> 00:03:24,460