Creating a Binary Search in Python (Summary)

Creating a Binary Search in Python Liam Pulsifer 00:44

Now you know the binary search algorithm inside and out. You can flawlessly implement it yourself, or take advantage of the standard library in Python. Having tapped into the concept of time-space complexity, you’re able to choose the best search algorithm for the given situation.

Now you can:

Use the bisect module to do a binary search in Python
Implement binary search in Python recursively and iteratively
Recognize and fix defects in a binary search Python implementation
Analyze the time-space complexity of the binary search algorithm
Search even faster than binary search

Download

Sample Code (.zip)

3.3 KB

Download

Course Slides (.pdf)

840.3 KB

Congratulations, you made it to the end of the course! What’s your #1 takeaway or favorite thing you learned? How are you going to put your newfound skills to use? Leave a comment in the discussion section and let us know.

00:00 Over the course of this series, you’ve learned all about the binary search and about search algorithms in general. You’ve learned about several different search algorithms and why you might or might not want to use them.

00:10 You’ve learned many different ways to perform a binary search in Python. With the bisect module, on your own, in a couple of different fashions—you’ve really learned it all.

00:19 You’ve also learned some common pitfalls to avoid when you’re implementing binary search. And then you learned a lot about the time and space complexity of binary search, of algorithms in general, and when using hash tables to try to search even faster than binary search.

00:35 Please do drop a comment below and tell me what you liked and anything else that you’d like to learn more about in the future. Thanks again!

hughdbrown on Oct. 27, 2020

You mentioned that you should be careful to avoid integer overflow in calculating your middle index. Your preferred way was:

middle = left + (right - left) // 2

And this is fine, but there is a related way to do division by two:

middle = left + (right - left) >> 1

And the problem is that integer-division has different precedence from right-shift. To see this, take an example:

>>> left, right = 2, 5
>>> print(left + (right - left) // 2)
3
>>> print(left + (right - left) >> 1)
2

And the problem is that right-shift has lower precedence than plus, so left + (right - left) >> 1 is the same as (left + (right - left)) >> 1, and that is not what you want.

I’d recommend using parentheses so clearly mark the desired grouping since it is easy to get wrong.

Ghani on Nov. 3, 2020

Very informative tutorial; many thanks!

Jon David on Nov. 3, 2021

Thanks, Liam!

Become a Member to join the conversation.