Preview
Video Player
00:00
00:00
Binary Search in Code
10:03In the last video we left off with an implementation of linear search. Let's do the same for binary search so that we get an understanding of how this is represented in code.
In the last video, we left off with
an implementation of linear search.
0:00
Let's do the same for binary search so
0:04
that we get an understanding of
how this is represented in code.
0:06
So we'll do this in a new file,
back to File, New File.
0:10
And we'll name this one binary_search.py.
0:14
Like before, we're going to start
with a function named binary search.
0:20
So we'll say def binary_search.
0:24
That takes a list and a target.
0:27
If you remember, binary search
works by breaking the array or
0:31
list down into smaller sets until we
find the value we're looking for.
0:35
We need a way to keep track of
the position of the lists that we're
0:39
working with.
0:43
So let's create two variables, first and
0:44
last to point to the beginning and
end of the array.
0:47
So, first = 0.
0:50
Now, if you're new to programming,
0:54
list positions are represented by index
values that start at 0 instead of 1.
0:56
So here, we're setting first to 0 to
point to the first element in the list.
1:00
Last is going to point to
the last element in the list.
1:06
So we'll say, last = len(list)- 1.
1:09
Now, this may be confusing to you, so a
quick sidebar to explain what's going on.
1:15
Let's say we have a list
containing five elements.
1:20
If we called len on the list,
we should get five back,
1:23
because there are five elements.
1:25
But remember that because
the position number start at zero,
1:27
the last value is not at position five,
but at four.
1:31
In nearly all programming languages,
getting the position of the last element
1:35
in the list is obtained by determining
the length of the list and deducting 1,
1:40
which is what we're doing.
1:44
Okay, so we know where the first and last
positions are when we start the algorithm.
1:46
For our next line of code,
we're going to create a while loop.
1:51
A while loop takes a condition and
1:54
keeps executing the code inside the loop
until the condition evaluates to false.
1:57
For our condition, we're going to
say to keep executing this loop
2:02
until the value of first is less than or
equal to the value of last.
2:07
So while first less than or equal to last,
why you ask, why is this our condition?
2:12
Well, let's work through
this implementation and
2:20
then a visualization should help.
2:23
Inside the while loop, we're going to
calculate the mid point of our list since
2:24
that's the first step of binary search.
2:29
Mid point equal, so
we'll say first plus last, and
2:32
then we will use the floor division,
// here, divided by 2.
2:36
Now the two forward slashes here are what
Python calls a floor division operator.
2:42
What it does is it rounds down
to the nearest whole number.
2:48
So if we have eight element array
first is zero, last is seven,
2:51
if we divided 0+7,
which is 7 by 2, we'll get 3.5.
2:56
That 3.5 is not a valid index position so
you round the dot to 3,
3:02
using the floor division operator.
3:06
Okay, so now we have a midpoint.
3:08
The next step of binary search is to
evaluate whether the value at this
3:10
midpoint is the same as
the target we're looking for.
3:14
So say if list, and
value it midpoint, equals the target.
3:17
Well if it is, then we'll go ahead and
return the midpoint.
3:24
So say return midpoint.
3:28
The return statement terminates our
algorithm, and over here we're done.
3:31
This is our best case scenario.
3:35
Next, we'll say else if list at midpoint,
or
3:39
a value at midpoint,
is less than the target?
3:43
Now here, if the value is less, the value
at midpoint is less than the target,
3:47
then we don't care about any of
the values lower than the midpoint.
3:52
So we redefine first to point
to the value after the midpoint.
3:56
So we say midpoint+1.
4:01
Now if the value at the midpoint
is greater than the target,
4:04
then we can discard the values
after the midpoint and
4:08
redefine last to point to
the value prior to the midpoint.
4:11
So we say else: last = midpoint- 1.
4:15
Let's visualize this.
4:23
We're going to start with
a list of nine integers.
4:24
To make this easier to understand,
4:27
let's specify these integers to be of
the same value as its index position.
4:29
So we have a range of
values from zero to eight.
4:34
Our target is the worst case scenario.
4:37
We're looking for
the position of the value 8.
4:39
At the start, our algorithm sets
first to point to be indexed 0 and
4:42
last to point to the length of
the list minus 1 which is 8.
4:47
Next, we hit our while loop.
4:51
The logic of this loop is going to be
executed as long as the value of first is
4:53
not greater than the value of last.
4:58
Or as we have defined it,
we're gonna keep executing the contents of
5:00
the loop as long as first is less than or
equal to last.
5:05
On the first pass, this is true,
so we enter the body of the loop.
5:08
The midpoint is first plus last
divided by 2 and rounded down, so
5:13
we get a nice even 4.
5:17
The value at this position is 4.
5:19
Now, this is not equal to the target, so
5:21
we move to the first else/if for
is less than 8.
5:24
So now we redefine first to point
to midpoint plus 1, which is 5.
5:27
First is still less than last, so
we run through the body of the loop again.
5:33
The midpoint is now 6.
5:38
6 is less than 8, so
we move first to point to 7.
5:40
7 is still less than or equal to 8, so
we go for another iteration of the loop.
5:45
The midpoint is 7, oddly enough, and
7 is still less than the target.
5:51
So we move first to point to 8.
5:55
First is equal to last now.
5:58
But our condition says keep the loop
going as long as first is less than,
6:00
or equal to last.
6:06
So this is our final
time through the loop.
6:07
The mid-point is now 8, which makes the
value at the mid-point equal to the target
6:10
and we finally exit our algorithm and
return the position of the target.
6:15
Now, what if we had
executed all this code and
6:20
never hit a case where
midpoint equal the target?
6:22
Well, that would mean the list
did not contain the target value.
6:26
So after the while loop,
at the bottom, we'll return None.
6:29
We have several operations that make
up our binary search algorithm, so
6:35
let's look at the run time of each step.
6:39
We start by assigning values to first and
last.
6:42
The value assigned to last involves a call
to the len function to get the size of
6:46
the list.
6:51
But we already know this is a constant
time operation in Python so
6:51
both of these operations
run in constant time.
6:56
Inside a loop,
we have another value assignment, and
6:59
this is a simple division operation.
7:02
So again, the runtime is constant.
7:04
In the next line of code,
we're reading a value from the list and
7:06
comparing the midpoint to the target.
7:10
Both of these again
are constant time operations.
7:13
The remainder of the code is just a series
of comparisons and value assignments and
7:16
we know that these are all
constant time operations as well.
7:21
So if all we have are a series
of constant time operations,
7:25
why does this algorithm have, in the worst
case, a longer rhythmic run time.
7:28
It's hard to evaluate by just
looking at the code, but
7:33
the while loop is what
causes the runtime to grow.
7:37
Even though all we're doing
is a comparison operation,
7:40
by redefining first and last over here, or
7:44
rather in the last two steps over here,
we're asking the algorithm to
7:47
run as many times as it needs until
first is equal or greater than last.
7:52
Now each time the loop does this, the size
of the data set, the size of the list,
7:58
grows smaller by a certain factor,
until it approaches a single element,
8:02
which is what results in
the logarithmic runtime.
8:07
Okay, just like with linear search,
let's test that our algorithm works.
8:10
So we go back to linear_search.py,
and we're going to copy paste.
8:16
So, Cmd+C to copy if you're on Mac,
8:20
then go back to binary search,
and at the bottom, oops!
8:23
We're going to paste in
that verify function.
8:27
Okay, we'll also go back and
grab these numbers.
8:30
You know what, let's go ahead and
copy all, all of these things,
8:34
so numbers and the two verified cases.
8:38
We'll paste that in as well, and
the only thing we need to change here is,
8:40
instead of calling linear search,
this is going to call binary search.
8:44
Okay, we'll hit Cmd+S to save the file,
and then I'm going to drag
8:50
up my console and we'll run python
binary_search.py and hit Enter.
8:56
And you'll see, just like before,
we get the same results back.
9:01
Now, note that an extremely important
distinction needs to be made here.
9:05
The numbers list that we've defined for
our test cases,
9:09
right here, has to be sorted.
9:13
The basic logic of binary search relies
on the fact that if the target is greater
9:16
than the midpoint, then our potential
values lie to the left, or vice versa.
9:22
Since the values are sorted
in ascending order.
9:27
If the values are unsorted,
our implementation of binary search
9:30
may return none,
even if the value exists in the list.
9:35
And just like that, you've written code
to implement two search algorithms.
9:39
How fun was that?
9:42
Hopefully, this course has shown you that
it isn't a topic to be afraid of, and
9:44
that algorithms, like any other topic
with code, can be broken down and
9:48
understood piece by piece.
9:53
Now, we have a working
implementation of binary search.
9:54
But there's actually more
than one way to write it.
9:58
So in the next video let's
write a second version.
10:00