Binary search finds things fast
I wrote a small interactive book to teach binary search.
Binary search is an algorithm that finds things fast.
When I was twelve and didn't know programming, my dad taught me about binary search. His explanation was so simple that it stuck with me.
I wrote a small interactive book to teach binary search the way he taught me.
The Binary Search Handbook is short and teaches by example.
First, download the book and try it for yourself. It will help illustrate the topics below.
In this post, I'll explain binary search in more detail.
What is binary search?
Binary search is an efficient algorithm for finding an item's position in a sorted array. It works by dividing the search range in half multiple times.
The array must be sorted for binary search to work.
The search begins in the middle of the array. If the target value matches the middle element, the search ends.
If the target value is less than the middle value, the search moves to the left half.
If the target value is higher than the middle value, the search moves to the right half.
This process continues until it finds the target or nothing is left to search.
Use Cases
Binary search is useful for cases like:
Checking if a value is in a sorted array: Determine if a specific element exists in a sorted list.
Finding the first occurrence of a value: Locate the first instance of a target value in a sorted array with or without duplicates.
Finding the insertion point: Identify the correct index to insert a new element to maintain order.
Finding a word in a dictionary
Finding a word in a dictionary is a great use case for binary search. The Binary Search Handbook illustrates this. A dictionary is a sorted list of words spread across many pages in a book. Let's see how binary search helps find a specific word.
Imagine you have a printed dictionary with thousands of words. Instead of checking each word one by one, binary search lets you find your word in just a few steps.
Step 1: Start in the Middle
Open your dictionary to the middle page. Let's say the dictionary has 300 pages. Open to page 150. This is your starting point.
Step 2: Ask a Simple Question
Look at the first word on page 150 and ask, "Is the word I'm looking for before this word?" This yes/no question eliminates half of the search results. If the answer is yes, you only have to search the first half. If the answer is no, you only have to search the last half.
Step 3: Halve Your Search
Based on the answer, you either move to the middle of the first half or the second half of the dictionary. If the word is after page 150, go to the middle of the second half, page 225. If it’s before, go to the middle of the first half, page 75.
Repeat Until You Find It
Repeat this process: go to the middle of your current section and ask the same yes/no question. Each time, you cut the number of pages to search in half. This is the power of binary search.
Within a few guesses, you'll have only one page left. This is the page with your word. You can take this further and find the exact line with your word.
First, go to the middle of the page and ask the question. Depending on the answer, your word is on the top or bottom half of the page. Each time, you cut the number of words to search on the page in half. Repeat until there is only one word left.
Why It Works
Binary search is efficient because it reduces the number of pages to check by a large margin. Instead of looking through 300 pages, you can find the page in about 8 steps. That’s because each step narrows down the possibilities by half.
number of steps = log2(n)
A Fun Example
You can find a word you don't know using the same process. You only need a function to answer the question, "Is it before this?"
You can use this trick to find a word a friend is thinking of in a dictionary without them telling you the word. All they have to do is answer, "Is it before this?"
Big-O
O(log n)time complexity – Binary search halves the array each time. So, the maximum number of comparisons needed is the logarithm (base 2) of the number of elements.O(1)space complexity – Binary search uses the same amount of extra memory regardless of the input array size. It operates in place, only using a few extra variables to keep track of the search range.
Binary Search Tree
Binary search is an algorithm. Its cousin data structure is a Binary Search Tree (BST).
Binary search is great for static, sorted arrays. However, if you insert items into the array, you must resort. Sorting an array is expensive, with an O(n log n) to O(n²) complexity.
A Binary Search Tree fixes this by maintaining elements in sorted order. Each node in a BST has up to two children. The left child contains values less than the parent node. The right child contains values greater than the parent node. This structure ensures searches, inserts, and deletes perform in O(log n) time on average.
When to use Binary Search vs Binary Search Tree
Static Data (Binary Search): If the data is static (i.e., it doesn't change), a binary search on a sorted array is more efficient. The overhead of creating a BST is usually greater than sorting and searching a static array.
Dynamic Data (BST): A BST is more efficient for dynamic datasets with frequent inserts or deletes. BSTs provide efficient
O(log n)time complexity for operations. This is more efficient than repeatedly sorting an array for binary search.
That’s it.
Binary search is a simple yet powerful algorithm. A code example is at the end of this article.
If you enjoyed the Binary Search Handbook, consider sharing it with someone who might be interested in programming.
What I’m reading
I often take on more work than I should.
and wrote some tips to help with that in How to say "No" and win back your time as a software engineer.Don’t Criticise and YOU ARE WRONG! are great contradictory titles from
. They’ll both help you correct people without offending them.In Glue Work: The Hidden Hero of Team Success,
highlights those who work on often-overlooked tasks that hold a team together.
Example code
I've provided an example Python binary search implementation below. This should illustrate how a binary search algorithm works.
Python has efficient built-in functions, such as list.index, to find positions of a value in a list and bisect for binary search operations. You should use those instead of making your own.
This type of algorithm is generally called a “two-pointer”. That’s because it has two pointers, left and right, representing the bounds of the search window.
def binary_search(items: list[int], target: int) -> int:
# The left and right pointers represent the bounds
# of our search window.
# Initialize them to the entire index range.
# For example, if the initial list is
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
# It starts with left=0, right=9 and looks like this:
# [>0 1 2 3 4 5 6 7 8 9<]
left, right = 0, len(items) - 1
# Continue searching while there is a valid range.
# The loop stops when left is greater than right,
# meaning the target is not within the range.
while left <= right:
# Calculate the middle index by cutting the
# current search window in half.
middle = (left + right) // 2
# The first time around, left=0, right=9, middle=4
# [>0 1 2 3(4)5 6 7 8 9<]
# If the middle element is the target, return its index.
if items[middle] == target:
return middle
# If the target is greater than the middle element,
# narrow the search range to the right half.
elif items[middle] < target:
left = middle + 1
# The first time around, left=5, right=9, middle=4
# [ 0 1 2 3(4>5 6 7 8 9<]
# If the target is less than the middle element,
# narrow the search range to the left half.
else:
right = middle - 1
# The first time around, left=0, right=3, middle=4
# [>0 1 2 3<4)5 6 7 8 9]
# If the target is not found in the array, return -1.
return -1
assert binary_search([1, 2, 3, 4, 5], 3) == 2
assert binary_search([1, 2, 3, 4, 5], 1) == 0
assert binary_search([1, 2, 3, 4, 5], 5) == 4
assert binary_search([1, 2, 3, 4, 5], 6) == -1
assert binary_search([], 3) == -1
assert binary_search([1], 1) == 0
assert binary_search([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 7) == 6
assert binary_search([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 2) == 1
assert binary_search([1, 3, 5, 7, 9], 4) == -1