Heads up! To view this whole video, sign in with your Courses account or enroll in your free 7-day trial. Sign In Enroll
Preview
Start a free Courses trial
to watch this video
The algorithm Jon used, linear search, seemed familiar to us and you could understand it because it's how most of us search for things in real life anyway. Brittney's approach on the other hand got results quickly but was a bit harder to understand so let's break it down.
This video doesn't have any notes.
Related Discussions
Have questions about this video? Start a discussion with the community and Treehouse staff.
Sign upRelated Discussions
Have questions about this video? Start a discussion with the community and Treehouse staff.
Sign up
The algorithm John used,
linear search, seemed familiar to us.
0:00
And you could understand it because
it's how most of us search for
0:03
things in real life anyway.
0:06
Britney's approach, on the other hand,
0:08
got results quickly, but
it was a bit harder to understand.
0:10
So let's break it down.
0:13
[SOUND] Just like John's approach, Britney
started with a series of values, or
0:14
list of numbers, as her input.
0:18
Where John just started at the beginning
of the list and searched sequentially,
0:20
Britney's strategy is to always
start in the middle of the range.
0:25
From there,
she asks a comparison question,
0:28
is the number in the middle of the range
equal to the answer she's looking for?
0:31
And if it's not, is it greater than or
less than the answer?
0:36
If it's greater than,
0:39
she can eliminate all the values less
than the one she's currently evaluating.
0:41
If it's lesser than the answer,
0:46
she can eliminate all the values greater
than the one she's currently evaluating.
0:47
With the range of values
that she's left over with,
0:52
she repeats this process until
she arrives at the answer.
0:55
[SOUND] Let's visualize how she
did this by looking at Round 3.
0:58
[SOUND] In Round 3,
the number of values in the range was 100.
1:03
The answer was 5.
1:06
The bar here represents the range
of values, 1 on the left, 100 on
1:07
the right and this pointer represents
the value Britney chooses to evaluate.
1:11
So she starts in the middle at 50,
she asks is it equal to the answer?
1:16
I say it's too high.
1:21
So this tells her that the value she is
evaluating is greater than our target
1:22
value.
1:27
Which means there's no point in searching
any of the values to the right of 50,
1:27
that is values greater
than 50 in this range.
1:32
So she can discard those
values altogether.
1:35
[SOUND] She only has to consider
values from 1 to 50 now.
1:38
[SOUND] The beauty of this strategy, and
1:42
the reason why Britney was able to
find the answer in such few turns,
1:44
is that with every value she evaluates,
she can discard half of the current range.
1:48
On her second turn, [SOUND] she picks the
value in the middle of the current range,
1:53
which is 25.
1:57
She asks the same question.
1:58
I say that the value is too high again.
2:00
And this tells her that she can
discard everything greater than 25.
2:03
[SOUND] And
the range of value drops from 1 to 25.
2:07
Again, she evaluates the number
in the middle, roughly.
2:10
So that'd be 13, here.
2:13
I tell her, this is still too high.
2:15
She discards the values greater,
moves to value 7, which is still too high.
2:17
Then she moves to 4, which is now too low.
2:21
She can discard everything less than 4,
which leaves the numbers 4 through 7.
2:24
Here, she picks 6, which is too high,
which only leaves one value, 5.
2:29
This seems like a lot of work.
2:34
But being able to get rid of
half the values with each turn
2:36
is what makes this algorithm
much more efficient.
2:40
Now, there's one subtlety
to using binary search, and
2:43
you might have caught on to this.
2:46
For this search method to work, as we've
mentioned, the values need to be sorted.
2:47
[SOUND] With linear search, it doesn't
matter if the values are sorted.
2:52
Since a linear search algorithm
just progresses sequentially,
2:55
checking every element in the list.
2:59
If the target value exists in the list,
it will be found.
3:02
Let's say this range of values,
1 to 100, was unsorted.
3:05
Britney would start at the middle
with something like 14 and
3:09
ask if this value was too low or too high?
3:12
I say it's too high so
she discards everything less than 14.
3:15
Now, this example starts to
fall apart here, because well,
3:19
Brittany knows what numbers are less
than 14 and greater than 1.
3:22
She doesn't need an actual
range of values to solve this.
3:26
A computer, however, does need that.
3:29
Remember, search algorithms are run
against lists containing all sorts
3:31
of data.
3:36
It's not always just a range
of values containing numbers.
3:37
In a real use case of binary search,
which we're going to implement in a bit.
3:39
The algorithm wouldn't return the target
value because we already know
3:44
that it's a search algorithm.
3:48
So we're providing
something to search for.
3:50
Instead, what it returns is the position
in the list that the target occupies.
3:52
Without the list being sorted,
3:56
a binary search algorithm will discard all
the values to the left of 14 which over
3:58
here could include the position
where our target value is.
4:03
Eventually we get a result back saying
the target value doesn't exist in the list
4:06
which is inaccurate.
4:10
Earlier when defining linear simple search
I said that the input was a list of
4:12
values and
the output was the target value or
4:17
more specifically the position
of the target value in the list.
4:19
So at binary search there's also that
pre-condition the input list must be
4:24
sorted.
4:28
So let's formally define binary search.
4:29
First the input a sorted list of values.
4:31
The output,
4:35
the position in the list of the target
value we're searching for, [SOUND] or
4:35
some sort of values indicate that
the target does not exist in the list.
4:40
Remember our guidelines for
defining an algorithm?
4:44
Let me put those up again really quick.
4:47
The steps in the algorithm need
to be in a specific order.
4:48
The steps also need to be very distinct.
4:52
The algorithms should produce a result and
4:54
finally the algorithms should
complete in a finite amount of time.
4:57
Let’s use those to define this algorithm.
5:01
Step one, [SOUND] we determine
the middle position of the sorted list.
5:04
Step two, we compare the element in
the middle position to the target element.
5:07
Step three, if the elements match,
we return the middle position and end.
5:12
[SOUND] If they don't match, in step four,
we check whether the element in
5:17
the middle position is smaller
than the target element.
5:21
[SOUND] If it is, then we go back to
step two, with a new list that goes from
5:24
the middle position of the current
list to the end of the current list.
5:29
[SOUND] In step five, if the element
in the middle position is greater than
5:33
the target element,
then again [SOUND] we go back to step two.
5:37
With a new list that goes to the start
of the current list to the middle
5:40
of the current list.
5:44
[SOUND] We repeat this process
until the target element is found.
5:45
Or until a sub-list
contains only one element.
5:49
If that single element sub-list
does not match the target elements,
5:52
then we end the algorithm.
5:57
Indicating that the element
does not exist in the list.
5:59
Okay, so
6:02
that is the magic behind how Britney
managed to solve around much faster.
6:02
In the next video let's talk about
the efficiency of binary search
6:07
You need to sign up for Treehouse in order to download course files.
Sign upYou need to sign up for Treehouse in order to set up Workspace
Sign up