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
Now that we have our list of names sorted, we can use the Binary Search algorithm on it. Let's see if we can use it to speed up our search for the indexes of 100 names.
See the instruction step following this video for the code!
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
Now that we have our list of names sorted,
0:00
we can use the binary
search algorithm on it.
0:02
Let's see if we can use it to speed up
our search for the indexes of 100 names.
0:04
Binary search keeps narrowing down
the list until it has the value
0:09
it's looking for.
0:13
It's faster than linear search
because it discards half the potential
0:14
matches each time.
0:18
Our code here at the top of our binary
search script is unchanged from
0:19
the previous scripts.
0:22
We just call the load strings function to
load our 100,000 sorted names from a file.
0:23
Here we've hard coded the list of 100
names we're going to sort for again.
0:28
It's identical to list from
a linear search script,
0:32
except that I've again changed the last
two names to correspond to the names
0:35
on the first and
last lines of the file we'll be loading.
0:38
Now let's write the function that will
implement our binary search algorithm.
0:42
Like the linear search function before,
it will take two arguments.
0:46
The first is the list we're
going to search through, and
0:49
the second is the target
value we'll be searching for.
0:52
Again, the binary search function will
return the index it found the value at, or
0:55
the special value none if it wasn't found.
1:00
Binary search is faster than linear search
because it discards half the values it
1:02
has to search through each time.
1:06
To do this,
1:08
it needs to keep track of a range that
it still needs to search through.
1:09
To start, that range is going
to include the full list.
1:13
The first variable will track the lowest
index in the range we're searching.
1:16
To start it's going to be zero,
the first index in the full list.
1:20
Likewise, the last variable will track
the highest index in the range we're
1:25
searching.
1:29
To start, we'll set it to
the highest index in the full list.
1:29
If the first and last variables are equal,
1:33
then it means the size of the search range
has shrunk to zero and there is no match.
1:35
Until that happens though,
we'll keep looping to continue the search.
1:40
We want to divide the list of
potential matches in half each time.
1:44
To do that,
1:47
we need to check the value that's in the
middle of the range we're searching in.
1:48
We add the indexes in the first and
1:52
last variables,
then divide by two to get their average.
1:54
We might get a fractional number,
which can't be used as a list index, so
1:58
we also round down using Python's
double-slash floor division operator.
2:01
All this will give us
the index of the list element
2:07
that's the midpoint of
the range we're searching.
2:09
We store that in the midpoint variable.
2:12
Whoops, looks like my
indentation got mixed up there.
2:14
Let me fix that real quick.
2:18
There we go.
2:19
Now we test whether the list element at
the midpoint matches the target value.
2:20
If it does, we return the midpoint
index without looping any further,
2:28
our search is complete.
2:32
Otherwise, if the midpoint element's
value is less than the target value, Then
2:34
we know that our target value can't be at
the midpoint or any index prior to that.
2:41
So we move the new start of our search
range to just after the old midpoint.
2:46
Otherwise, the midpoint element's
value must have been greater than
2:51
the target value.
2:54
We know that our target value can't be at
the midpoint, or any index after that, so
2:56
we move the new end of our search
range to just before the old midpoint.
3:00
By unindenting here,
we mark the end of the loop.
3:05
If the loop completes,
3:07
it means the search range shrank to
nothing without our finding a match.
3:09
And that means there's no
matching value in the list.
3:12
So we return the special Python
value none to indicate this.
3:15
Lastly, just as we did in
our linear search script,
3:19
we need to search for
each of the 100 names.
3:22
We loop over each name
in our hard-coded list.
3:25
And we call the binary_search function
with the sorted list of names we're going
3:28
to load from the file and
the current name we're searching for.
3:32
We have store the returned list
index in the index variable.
3:36
And finally, we print that variable.
3:40
Let's save this and
go to our console and try running it.
3:44
Python binary_search.py, and
3:47
it's important to give it
the name of the sorted file.
3:51
If it loads the unsorted file,
the binary search won't work.
3:53
So names/sorted,text.
3:56
Again, it prints out the list
of indexes for each name.
4:00
I once again set it up so the last two
items in the list of names we are gonna
4:05
search for corresponded to the first and
last name in the file.
4:09
So it returned an index of zero for
the second to last name.
4:12
And you can see that name.
4:18
Here's the second to last name,
Aaron Augustine.
4:24
You can see that name here
on line one of the file.
4:29
And for the last name,
it returned an index of 109873.
4:32
And you can see that
name here on line 109874.
4:37
Let's check the third to last name for
good measure.
4:45
It looks like an index of 97022 was
printed for that name, Stephen Deras.
4:48
Let's search for
Steven Deras within the file.
4:56
And here it is, on line 97023.
5:01
Remember that line numbers
start on one instead of zero,
5:05
so this actually matches up with
the printed list index of 97022.
5:09
It looks like our binary search
script is working correctly.
5:14
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