• +91-9142290450

  • Hajipur, Bihar, 844101

☰
❮
❯

Python Binary Search

← Previous Next →

Binary search is one of the fastest searching algorithms used in programming. It works by dividing the search range in half again and again, which makes it much faster than linear search. The only requirement is that the list must already be sorted. Because of its speed and reliability, binary search is used in databases, search engines, system-level code and any application that needs quick lookups.

In this tutorial, you’ll learn how binary search works, why it’s so efficient, how to implement it in Python, the step-by-step flow of the algorithm and many real-world examples. This chapter builds your foundation for more advanced searching and algorithmic thinking.

What Is Binary Search?

Binary search is an algorithm that repeatedly splits the search interval into two halves. Instead of checking every element, it checks the middle element first. If the target is smaller, the search continues in the left half. If it's larger, the search moves to the right half. This halves the search space at every step.

This approach reduces the time drastically compared to scanning one element at a time.

Condition for Binary Search

Binary search only works when:

  • The list is sorted

  • You can access elements by index

Without sorting, the left and right comparisons won’t make sense, so the algorithm will fail.

How Binary Search Works Step by Step

Consider a sorted list:

[5, 9, 14, 22, 30, 41, 56]

If the target is 22, the process goes like this:

  1. Look at the middle element → 22

  2. It matches, so return the index

If the target is 30:

  1. Mid → 22

  2. 30 is larger → search right half

  3. New mid → 30

  4. Match found

Each step cuts the search space in half, which is what makes binary search efficient.

Why Use Binary Search?

Binary search is helpful because:

  • It is extremely fast

  • Time complexity is O(log n)

  • Works well on large sorted lists

  • Reduces comparisons

  • Used in critical systems like indexing, compilers and OS internals

The log-based reduction makes it one of the most powerful searching methods.

Binary Search Using a Loop

Here’s an iterative version:

def binary_search(data, target):
    low = 0
    high = len(data) - 1

    while low <= high:
        mid = (low + high) // 2

        if data[mid] == target:
            return mid
        elif data[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

This approach uses two pointers and keeps narrowing the window.

Binary Search Using Recursion

A recursive version looks like this:

def binary_search_recursive(data, target, low, high):
    if low > high:
        return -1

    mid = (low + high) // 2

    if data[mid] == target:
        return mid
    elif data[mid] < target:
        return binary_search_recursive(data, target, mid + 1, high)
    else:
        return binary_search_recursive(data, target, low, mid - 1)

Call it like this:

binary_search_recursive(data, target, 0, len(data) - 1)

Example Usage

data = [3, 7, 12, 18, 25, 40]
result = binary_search(data, 18)

print(result)

Output:

3

This shows the index where the number exists.

Time Complexity of Binary Search

Binary search is fast because it cuts the search area in half each time.

  • Best case: O(1)

  • Worst case: O(log n)

  • Average case: O(log n)

This efficiency makes binary search ideal for large datasets.

When Binary Search Works Best

Use binary search when:

  • Data is sorted

  • You search frequently

  • Performance is important

  • You work with large collections

Databases, dictionaries and system-level programs rely on this logic.

When Binary Search Is Not Suitable

Avoid binary search when:

  • The list is not sorted

  • Data changes very frequently

  • Sorting cost is high

  • Elements cannot be indexed

In such cases, linear search may be simpler.

Real-Life Uses of Binary Search

Searching a word in a dictionary

You open the book near where the word should be.

Guessing a number game

You ask if the guess is higher or lower.

Auto-suggest systems

Search engines narrow down matches quickly.

Library book arrangement

Books are already sorted, helping fast lookup.

Stock price lookup

Sorted time-series data is searched quickly.

Binary search maps closely to many real tasks.

Step-by-Step Example

Sorted list:

[2, 6, 11, 15, 20, 28, 35]

Target: 15

Steps:

  1. mid → 15 (match)

  2. Return index

Target: 28

  1. mid → 15

  2. 28 > 15 → search right

  3. new mid → 28

  4. match

This shows the efficiency.

Practical Examples

Example 1: Search number

print(binary_search([1, 4, 7, 12], 7))

Example 2: Search string

items = ["apple", "banana", "cherry", "date"]
print(binary_search(items, "cherry"))

Example 3: Search last element

print(binary_search([10, 20, 30, 40], 40))

Example 4: Not found case

print(binary_search([2, 4, 6, 8], 5))

Example 5: Recursive search

binary_search_recursive([3, 10, 22], 22, 0, 2)

Example 6: Search in a list of tuples (sorted)

pairs = [(1,"a"), (3,"b"), (5,"c")]
print(binary_search(pairs, (5,"c")))

Example 7: Search in sorted floats

nums = [1.2, 3.5, 4.7, 6.8]
print(binary_search(nums, 4.7))

Example 8: Search date strings

dates = ["2021-01-01", "2021-01-05", "2021-01-10"]
print(binary_search(dates, "2021-01-05"))

Example 9: Search in large dataset

data = list(range(100000))
print(binary_search(data, 56789))

Example 10: Check sorted before search

values = [5, 3, 2]
if values == sorted(values):
    print(binary_search(values, 2))

Summary of the Tutorial

Binary search is a fast and efficient algorithm that works on sorted data by splitting the range in half until the target is found. You learned how the algorithm works, how to write iterative and recursive versions, where it performs best and where it should be avoided. Binary search is a foundation for many advanced algorithms and real-world systems.

Practice Questions

Q1. Write a Python program to perform binary search on a sorted list of 10 elements.

Q2. Write a Python program to modify the binary search function to return True or False instead of index.

Q3. Write a Python program to accept a list and a target value from the user and search using binary search.

Q4. Write a Python program to implement binary search using recursion.

Q5. Write a Python program to count and print the number of comparisons made during binary search.

Q6. Write a Python program to return all occurrences of the target value in case of duplicates.

Q7. Write a Python program to perform binary search on a descending sorted array (reverse order logic).

Q8. Write a Python program to use the bisect module to find insertion point of a value in a sorted list.

Q9. Write a Python program to compare execution time of binary search vs linear search.

Q10. Write a Python program to handle invalid input types using try/except in binary search.

← Previous Next →

Try a Short Quiz.

coding learning websites codepractice

No quizzes available.

Python

online coding class codepractice

Introduction to Python

Python Basics

Cotrol Structures

Data Structures

Date and Time

Functions and Module

File Handling

Python OOP

Advanced Concepts

Python DSA

Searching Algorithms

Sorting Algorithms

codepractice logo
Login
Go Back Top