Text of realpython.com › binary-search-python as Styx crawled it on Nov 20, 2026. The page may have changed since. Only its words are kept, without pictures or layout, and only the first part of a long page.

Open the live page

How to Do a Binary Search in Python – Real Python

How to Do a Binary Search in Python by Bartosz Zaczyński Updated Nov 14, 2026 Reading time estimate 1h 1m intermediate algorithms Table of Contents Remove ads Recommended Course Creating a Binary Search in Python (1h 10m) 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: Get Sample Code: Click here to get the sample code you’ll use to learn about binary search in Python in this tutorial.

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: Language: Shell $ 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.

Remove ads 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: Language: Text 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. Note: As a rule of thumb, you should avoid parsing files manually because you might overlook edge cases . For example, in one of the fields, the delimiting tab character could be used literally inside quotation marks, which would break the number of columns.

Whenever possible, try to find a relevant module in the standard library or a trustworthy third-party one. Ultimately, you want to end up with two text files at your disposal: names.txt sorted_names.txt One will contain a list of names obtained by cutting out the second column from the original TSV file: Language: Text 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: Language: Python def load_names ( path ): with open ( path ) as text_file : return text_file . read () . splitlines () names = load_names ( "names.txt" ) sorted_names = load_names ( "sorted_names.txt" ) This code returns a list of names pulled from the given file. Note that calling .splitlines() on the resulting string removes the trailing newline character from each line.

As an alternative, you could call text_file.readlines() , but that would keep the unwanted newlines. Measure the Execution Time To evaluate the performance of a particular algorithm, you can measure its execution time against the IMDb dataset. This is usually done with the help of the built-in time or timeit modules, which are useful for timing a block of code. You could also define a custom decorator to time a function if you wanted to.

The sample code provided uses time.perf_counter_ns() , introduced in Python 3.7, because it offers high precision in nanoseconds. Understanding Search Algorithms Searching is ubiquitous and lies at the heart of computer science. You probably did several web searches today alone, but have you ever wondered what searching really means? Search algorithms take many different forms. For example, you can: Do a full-text search Match strings with fuzzy searching Find the shortest path in a graph Query a database Look for a minimum or maximum value In this tutorial, you’ll learn about searching for an element in a sorted list of items, like a phone book.

When you search for such an element, you might be asking one of the following questions: Question Answer Is it there? Yes Where is it? On the 42nd page Which one is it? A person named John Doe The answer to the first question tells you whether an element is present in the collection. It always holds either true or false . The second answer is the location of an element within the collection, which may be unavailable if that element was missing.

Finally, the third answer is the element itself, or a lack of it. Note: Sometimes there might be more than one correct answer due to duplicate or similar items . For example, if you have a few contacts with the same name, then they will all fit your search criteria. At other times, there might only be an approximate answer or no answer at all. In the most common case, you’ll be searching by value , which compares elements in the collection against the exact one you provide as a reference.

In other words, your search criteria are the entire element, such as a number, a string, or an object like a person. Even the tiniest difference between the two compared elements won’t result in a match. On the other hand, you can be more granular with your search criteria by choosing some property of an element, such as a person’s last name. This is called searching by key because you pick one or more attributes to compare.

Before you dive into binary search in Python, let’s take a quick look at other search algorithms to get a bigger picture and understand how they work. Remove ads Random Search How might you look for something in your backpack? You might just dig your hand into it, pick an item at random, and see if it’s the one you wanted. If you’re out of luck, then you put the item back, rinse, and repeat. This example is a good way to understand random search , which is one of the least efficient search algorithms.

The inefficienc

The rest of this page is on the live site.