Hint: You can adjust the default video playback speed in your account settings.
Hint: You can set your subtitle preferences 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 refer to our video player troubleshooting guide for assistance.

Creating a Binary Search in Python (Overview)

Liam Pulsifer
Creating a Binary Search in Python Liam Pulsifer 02:14
Recommended Tutorial Course Slides (.pdf) Sample Code (.zip) Ask a Question

Binary search is a classic algorithm in computer science. It often comes up in programming contests and technical interviews. Implementing binary search turns out to be a challenging task, even when you understand the concept. Unless you’re curious or have a specific assignment, you should always leverage existing libraries to do a binary search in Python or any other language.

In this course, you’ll learn how to:

  • Use the bisect module to do a binary search in Python
  • Implement a binary search in Python both 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

This course assumes you’re a student or an intermediate programmer with an interest in algorithms and data structures. At the very least, you should be familiar with Python’s built-in data types, such as lists and tuples. In addition, some familiarity with recursion, classes, data classes, and lambdas will help you better understand the concepts you’ll see in this course.

Download

Sample Code (.zip)

 3.3 KB
Download

Course Slides (.pdf)

 840.3 KB

00:00 Hi, and welcome to this Real Python video tutorial series on the binary search in Python. Over the course of this series, you’ll learn to recognize the strengths and weaknesses of several different search algorithms so that you understand why and when to use the binary search in Python.

00:18 Then you’ll learn two different methods of actually performing a binary search, with the bisect module—which is in-built in Python—and then in your own implementation, in both recursive and iterative paradigms.

00:30 Then you’ll learn how to recognize and fix some common defects in a Python binary search implementation, and you’ll get into the theory of the binary search by analyzing the time and space complexity of the binary search algorithm and by investigating ways to search even faster than binary search, using hash-based paradigms.

00:50 The first and most important question is “What exactly is a binary search?”

00:55 Simply put, a binary search is a method of searching—or simply looking through—a collection in order to find a certain element. So if I have a list x with the elements 1, 2, 4, 6, and 9, then I might call bin_search() (binary search) on x with the search item 4,

01:15 and then bin_search() would return 2, to indicate that 4 can be found at the second index of the list x.

01:24 Now, you might also implement a binary search as a strict contains() function, so this might return True to indicate that 4 is in that item, rather than the exact index. But over the course of this series, I’ll mostly work with the index version. Unlike some other search algorithms, a binary search requires the collection to be sorted, but it leverages this fact to run really, really quickly for pretty much all inputs. And when I say “really quickly,” I mean orders of magnitude more quickly than many other search algorithms, so it’s quite useful. Now that you understand the basic idea of binary search, let me take you on a quick detour to talk about some of the data and benchmarking that I’ll do throughout this series to illustrate the performance of binary search.

Become a Member to join the conversation.