How to Do a Binary Search in Python

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 tutorial, 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 tutorial 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 tutorial.

Below you’ll find a link to the sample code you’ll see throughout this tutorial, which requires Python 3.7 or later to run:

Benchmarking

In the next section of this tutorial, you’ll be using a subset of the Internet Movie Database (IMDb) to benchmark the performance of a few search algorithms. This dataset is free of charge for personal and non-commercial use. It’s distributed as a bunch of compressed tab-separated values (TSV) files, which get daily updates.

To make your life easier, you can use a Python script included in the sample code. It’ll automatically fetch the relevant file from IMDb, decompress it, and extract the interesting pieces:

$ python download_imdb.py Fetching data from IMDb... Created "names.txt" and "sorted_names.txt" 

Be warned that this will download and extract approximately 600 MB of data, as well as produce two additional files, which are about half of that in size. The download, as well as the processing of this data, might take a minute or two to complete.

Download IMDb

To manually obtain the data, navigate your web browser to https://datasets.imdbws.com/ and grab the file called name.basics.tsv.gz, which contains the records of actors, directors, writers, and so on. When you decompress the file, you’ll see the following content:

nconst primaryName birthYear deathYear (...) nm0000001 Fred Astaire 1899 1987 (...) nm0000002 Lauren Bacall 1924 2014 (...) nm0000003 Brigitte Bardot 1934 \N (...) nm0000004 John Belushi 1949 1982 (...) 

It has a header with the column names in the first line, followed by data records in each of the subsequent lines. Each record contains a unique identifier, a full name, birth year, and a few other attributes. These are all delimited with a tab character.

There are millions of records, so don’t try to open the file with a regular text editor to avoid crashing your computer. Even specialized software such as spreadsheets can have problems opening it. Instead, you might take advantage of the high-performance data grid viewer included in JupyterLab, for example.

Read Tab-Separated Values

There are a few ways to parse a TSV file. For example, you can read it with Pandas, use a dedicated application, or leverage a few command-line tools. However, it’s recommended that you use the hassle-free Python script included in the sample code.

Ultimately, you want to end up with two text files at your disposal:

1. names.txt
2. sorted_names.txt

One will contain a list of names obtained by cutting out the second column from the original TSV file:

Fred Astaire Lauren Bacall Brigitte Bardot John Belushi Ingmar Bergman ... 

The second one will be the sorted version of this.

Once both files are ready, you can load them into Python using this function: