Creating a Binary Search in Python (Overview)
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
bisectmodule 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.
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.