1
00:00:00,000 --> 00:00:13,300

2
00:00:13,300 --> 00:00:15,010
>> ROB BOWDEN: Hi, I'm Rob.

3
00:00:15,010 --> 00:00:16,790
How do we employ a binary search?

4
00:00:16,790 --> 00:00:18,770
Let's find out.

5
00:00:18,770 --> 00:00:23,400
So, note that this search we're going
to implement recursively.

6
00:00:23,400 --> 00:00:27,470
You could also implement binary search
iteratively, so if you did that,

7
00:00:27,470 --> 00:00:29,280
that's perfectly fine.

8
00:00:29,280 --> 00:00:32,820
>> Now first, let's remember what the
parameters to search are meant to be.

9
00:00:32,820 --> 00:00:36,120
Here, we see int value, which is
supposed to be the value the user is

10
00:00:36,120 --> 00:00:37,320
searching for.

11
00:00:37,320 --> 00:00:40,800
We see the int values array, which
is the array in which we're

12
00:00:40,800 --> 00:00:42,520
searching for value.

13
00:00:42,520 --> 00:00:45,602
And we see int n, which is
the length of our array.

14
00:00:45,602 --> 00:00:47,410
>> Now, first thing first.

15
00:00:47,410 --> 00:00:51,350
We check to see if n equals 0, in
which case we return false.

16
00:00:51,350 --> 00:00:54,770
That's just saying if we have an empty
array, value is clearly not in an

17
00:00:54,770 --> 00:00:57,860
empty array, so we can return false.

18
00:00:57,860 --> 00:01:01,250
>> Now, we actually want to do the binary
search part of binary search.

19
00:01:01,250 --> 00:01:04,780
So, we want to find the middle
element of this array.

20
00:01:04,780 --> 00:01:09,130
Here, we say middle equals n divided
by 2, since the middle element is

21
00:01:09,130 --> 00:01:12,240
going to be the length of
our array divided by 2.

22
00:01:12,240 --> 00:01:15,040
Now we're going to check to see if the
middle element equals the value we're

23
00:01:15,040 --> 00:01:16,160
searching for.

24
00:01:16,160 --> 00:01:21,030
So if values middle equals value, we
can return true since we found the

25
00:01:21,030 --> 00:01:22,810
value in our array.

26
00:01:22,810 --> 00:01:26,380
>> But if that wasn't true, now
we need to do the recursive

27
00:01:26,380 --> 00:01:27,840
step of binary search.

28
00:01:27,840 --> 00:01:30,450
We need to search either to the
left of the array or to the

29
00:01:30,450 --> 00:01:32,320
middle of the array.

30
00:01:32,320 --> 00:01:39,280
So here, we say if values at middle is
less than value, that means that value

31
00:01:39,280 --> 00:01:41,350
was greater than the middle
of the array.

32
00:01:41,350 --> 00:01:45,790
So value must be to the right of the
element that we just looked at.

33
00:01:45,790 --> 00:01:48,090
>> So here, we're going to
search recursively.

34
00:01:48,090 --> 00:01:50,320
And we'll look at what we're passing
to this in a second.

35
00:01:50,320 --> 00:01:53,440
But we're going to search to the
right of the middle element.

36
00:01:53,440 --> 00:01:57,710
And in the other case, that means that
value was less than the middle of the

37
00:01:57,710 --> 00:02:00,660
array, and so we're going
to search to the left.

38
00:02:00,660 --> 00:02:03,520
Now, the left is going to be
a bit easier to look at.

39
00:02:03,520 --> 00:02:07,770
So, we see here that we're recursively
calling search where the first

40
00:02:07,770 --> 00:02:10,120
argument is, again, the value
we're looking over.

41
00:02:10,120 --> 00:02:14,970
The second argument is going to be the
array that we were searching over.

42
00:02:14,970 --> 00:02:17,090
And the last element now is middle.

43
00:02:17,090 --> 00:02:21,650
Remember the last parameter is our int
n, so that's the length of our array.

44
00:02:21,650 --> 00:02:25,310
>> In the recursive call to search, we're
now saying that the length of the

45
00:02:25,310 --> 00:02:27,230
array is middle.

46
00:02:27,230 --> 00:02:32,900
So, if our array was of size 20 and we
searched at index 10, since middle is

47
00:02:32,900 --> 00:02:36,930
20 divided by 2, that means we're
passing 10 as the new

48
00:02:36,930 --> 00:02:38,300
length of our array.

49
00:02:38,300 --> 00:02:41,910
Remember that when you have an array
of length 10, that means the valid

50
00:02:41,910 --> 00:02:45,450
elements are in indices 0 through 9.

51
00:02:45,450 --> 00:02:50,120
So this is exactly what we want to
specify our updated array-- the left

52
00:02:50,120 --> 00:02:53,010
array from the middle element.

53
00:02:53,010 --> 00:02:55,710
>> So, looking to the right is
a bit more difficult.

54
00:02:55,710 --> 00:03:00,170
Now first, let's consider the length
of the array to the right of the

55
00:03:00,170 --> 00:03:01,240
middle element.

56
00:03:01,240 --> 00:03:08,390
So, if our array was of size n, then the
new array will be of size n minus

57
00:03:08,390 --> 00:03:10,140
middle minus 1.

58
00:03:10,140 --> 00:03:12,530
So, let's think of n minus middle.

59
00:03:12,530 --> 00:03:18,710
>> Again, if the array were of size 20 and
we divide by 2 to get the middle,

60
00:03:18,710 --> 00:03:23,540
so the middle is 10, then n minus middle
is going to give us 10, so 10

61
00:03:23,540 --> 00:03:25,330
elements to the right of middle.

62
00:03:25,330 --> 00:03:27,780
But we also have this minus
1, since we don't want to

63
00:03:27,780 --> 00:03:29,700
include the middle itself.

64
00:03:29,700 --> 00:03:34,190
So n minus middle minus 1 gives us the
total number of elements to the right

65
00:03:34,190 --> 00:03:36,800
of the middle index in the array.

66
00:03:36,800 --> 00:03:41,870
>> Now here, remember that the middle
parameter is the values array.

67
00:03:41,870 --> 00:03:46,180
So here, we're passing an
updated values array.

68
00:03:46,180 --> 00:03:50,930
This values plus middle plus 1 is
actually saying recursively call

69
00:03:50,930 --> 00:03:56,460
search, passing in a new array, where
that new array starts in the middle

70
00:03:56,460 --> 00:03:59,370
plus one of our original values array.

71
00:03:59,370 --> 00:04:05,400
>> An alternate syntax for that, now that
you've started to see pointers, is

72
00:04:05,400 --> 00:04:10,170
ampersand values middle plus 1.

73
00:04:10,170 --> 00:04:17,149
So, grab the address of the middle
plus one element of values.

74
00:04:17,149 --> 00:04:23,690
>> Now, if you weren't comfortable
modifying an array like that, you

75
00:04:23,690 --> 00:04:28,900
could also have implemented this using
a recursive helper function, where

76
00:04:28,900 --> 00:04:31,680
that helper function takes
more arguments.

77
00:04:31,680 --> 00:04:36,610
So instead of taking just the value, the
array, and the size of the array,

78
00:04:36,610 --> 00:04:42,315
the helper function could take more
arguments, including the lower index

79
00:04:42,315 --> 00:04:45,280
that you would care about in the array
and the upper index that you care

80
00:04:45,280 --> 00:04:46,300
about the array.

81
00:04:46,300 --> 00:04:49,770
>> And so keeping track of both the lower
index and the upper index, you don't

82
00:04:49,770 --> 00:04:52,780
need to ever modify the
original values array.

83
00:04:52,780 --> 00:04:56,390
You can just continue to
use the values array.

84
00:04:56,390 --> 00:04:59,540
But here, notice we don't need a helper
function as long as we're

85
00:04:59,540 --> 00:05:01,760
willing to modify the original
values array.

86
00:05:01,760 --> 00:05:05,020
We're willing to pass in
an updated values.

87
00:05:05,020 --> 00:05:09,140
>> Now, we can't binary search over
an array that is unsorted.

88
00:05:09,140 --> 00:05:12,220
So, let's get this sorted out.

89
00:05:12,220 --> 00:05:17,650
Now, notice that sort is past two
parameters int values, which is the

90
00:05:17,650 --> 00:05:21,110
array that we're sorting, and int n,
which is the length of the array that

91
00:05:21,110 --> 00:05:22,250
we're sorting.

92
00:05:22,250 --> 00:05:24,840
So, here we want to implement
a sorting algorithm

93
00:05:24,840 --> 00:05:26,690
that is o of n squared.

94
00:05:26,690 --> 00:05:30,560
You could choose bubble sort, selection
sort, or insertion sort, or

95
00:05:30,560 --> 00:05:32,670
some other sort we haven't
seen in class.

96
00:05:32,670 --> 00:05:36,380
But here, we're going to
use selection sort.

97
00:05:36,380 --> 00:05:40,030
>> So, we're going to iterate
over the entire array.

98
00:05:40,030 --> 00:05:44,360
Well, here we see that we're iterating
from 0 to n minus 1.

99
00:05:44,360 --> 00:05:45,990
Why not all the way up to n?

100
00:05:45,990 --> 00:05:49,320
Well, if we've already sorted the first
n minus 1 elements, then the

101
00:05:49,320 --> 00:05:54,420
very last element what must already be
in the correct place, so sorting over

102
00:05:54,420 --> 00:05:56,520
the entire array.

103
00:05:56,520 --> 00:05:58,770
>> Now, remember how selection
sort works.

104
00:05:58,770 --> 00:06:01,950
We're going to go over the entire array
looking for the minimum value in

105
00:06:01,950 --> 00:06:04,480
the array and stick that
at the beginning.

106
00:06:04,480 --> 00:06:07,610
Then we're going to go over the entire
array again looking for the second

107
00:06:07,610 --> 00:06:10,410
smallest element, and stick that
in the second position in the

108
00:06:10,410 --> 00:06:12,100
array, and so on.

109
00:06:12,100 --> 00:06:14,330
So, that's what this is doing.

110
00:06:14,330 --> 00:06:17,290
>> Here, we're seeing that we're
setting the current minimum

111
00:06:17,290 --> 00:06:20,030
value to the i-th index.

112
00:06:20,030 --> 00:06:23,160
So on the first iteration, we're going
to consider the minimum value to be

113
00:06:23,160 --> 00:06:25,030
the start of our array.

114
00:06:25,030 --> 00:06:28,500
Then, we're going to iterate over the
remainder of the array, checking to

115
00:06:28,500 --> 00:06:31,870
see if there any elements smaller than
the one that we're currently

116
00:06:31,870 --> 00:06:33,900
considering the minimum.

117
00:06:33,900 --> 00:06:38,840
>> So here, values j plus one-- that's
less than what we are currently

118
00:06:38,840 --> 00:06:40,380
considering the minimum.

119
00:06:40,380 --> 00:06:42,940
Then we're going to update what
we think is the minimum to

120
00:06:42,940 --> 00:06:44,640
index j plus 1.

121
00:06:44,640 --> 00:06:48,540
So, do that across the entire array,
and after this for loop, minimum

122
00:06:48,540 --> 00:06:53,160
should be the minimum element from
the i-th position in the array.

123
00:06:53,160 --> 00:06:57,350
>> Once we have that, we can swap the
minimum value into the i-th position

124
00:06:57,350 --> 00:06:58,230
in the array.

125
00:06:58,230 --> 00:07:00,130
So this is just a standard swap.

126
00:07:00,130 --> 00:07:03,940
We store in a temporary value--
the i-th value in the array--

127
00:07:03,940 --> 00:07:08,460
put into the i-th value in the array the
minimum value that belongs there,

128
00:07:08,460 --> 00:07:13,580
and then store back into where the
current minimum value used to be the

129
00:07:13,580 --> 00:07:16,460
i-th value in the array, so
that we didn't lose it.

130
00:07:16,460 --> 00:07:20,510
>> So, that continues on
the next iteration.

131
00:07:20,510 --> 00:07:23,480
We'll start looking for the second
minimum value and insert that into the

132
00:07:23,480 --> 00:07:24,590
second position.

133
00:07:24,590 --> 00:07:27,440
On the third iteration, we'll look for
the third minimum value and insert

134
00:07:27,440 --> 00:07:31,550
that into the third position, and so
on until we have a sorted array.

135
00:07:31,550 --> 00:07:33,820
My name is Rob, and this
was selection sort.

136
00:07:33,820 --> 00:07:39,456