Join us and get access to hundreds of tutorials and a community of expert Pythonistas.

Unlock This Lesson

This lesson is for members only. Join us and get access to hundreds of tutorials and a community of expert Pythonistas.

Unlock This Lesson

Hint: You can adjust the default video playback speed in your account settings.
Hint: You can set the default subtitles language in your account settings.
Sorry! Looks like there’s an issue with video playback 🙁 This might be due to a temporary outage or because of a configuration issue with your browser. Please see our video player troubleshooting guide to resolve the issue.

Creating a Binary Search in Python (Summary)

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

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!

Become a Member to join the conversation.