Linear Search vs Binary Search in Python

When your Python list grows from 10 items to 10 million, the search algorithm you choose starts to matter a lot.

In this tutorial, you’ll learn the difference between linear search and binary search in Python, see how each works step by step, and measure how fast they are on real examples. By the end, you’ll know when a simple linear scan is enough and when you should refactor your code to use binary search on sorted data.

What Is Linear Search in Python?

Linear search (also called sequential search) is the simplest way to search in a list. You start from the first element and move one by one until you either find the target value or reach the end of the list.

This algorithm works on any Python list, whether it is sorted or not.

Linear search algorithm (in plain English)

1. Start from index 0.
2. Compare the current element with the target value.
3. If they are equal, return the index.
4. If not, move to the next index.
5. If you reach the end of the list without finding the value, return -1.

Linear search Python code

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

Example usage:

names = ["John", "Emily", "Michael", "Emma", "William"]
target_name = "Emma"

result = linear_search(names, target_name)

if result != -1:
    print(f"{target_name} found at index {result}")
else:
    print(f"{target_name} not found in the list")

This code will print:

Emma found at index 3

You can see the output in the screenshot below.

Linear search dry run (step-by-step)

Let’s dry-run the algorithm for the list [“John”, “Emily”, “Michael”, “Emma”, “William”] and target "Emma".

The algorithm stops as soon as it finds a match and returns the index.

Time complexity of linear search

• Time complexity (worst case): O(n), where n is the number of elements in the list.
• Intuition: If the item is at the very end or not present at all, you may have to check every element once, so the work grows linearly as the list gets bigger.

When is linear search good enough?

• Lists are small.
• Data is unsorted and you only search occasionally.
• You want the simplest possible implementation.

What Is Binary Search in Python?

Binary search is a much faster search algorithm, but it only works on sorted lists. It uses a divide-and-conquer strategy: it repeatedly divides the list in half to narrow down where the target could be.

Imagine looking for a name in a phonebook: you don’t flip page by page; you jump to the middle, then decide whether to go left or right based on alphabetical order. Binary search does the same with indices in a list.

Binary search algorithm (in plain English)

1. Make sure the list is sorted.
2. Set low to the first index and high to the last index.
3. Find the middle index mid = (low + high) // 2.
4. If arr[mid] is the target, return mid.
5. If arr[mid] is smaller than the target, search the right half (low = mid + 1).
6. If arr[mid] is larger than the target, search the left half (high = mid - 1).
7. Repeat steps 3–6 until low goes beyond high; if not found, return -1.

Binary search Python code

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

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

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

    return -1

Example usage with a sorted list of cities:

cities = [
    "Atlanta", "Boston", "Chicago", "Denver", "Houston",
    "Los Angeles", "New York", "San Francisco", "Seattle", "Washington"
]

target_city = "Houston"

result = binary_search(cities, target_city)

if result != -1:
    print(f"Binary Search: {target_city} found at index {result}")
else:
    print(f"Binary Search: {target_city} not found in the list")

Output:

Binary Search: Houston found at index 4

You can see the output in the screenshot below.

In this example, the binary search algorithm finds the target city “Houston” at index 4 in the sorted list of cities.

Binary search dry run example

Let’s dry-run the same function for cities and target “Seattle” to show multiple steps.

Initial list (indices shown):

Index:  0        1        2        3        4         5            6          7             8         9
Value:  Atlanta  Boston   Chicago  Denver   Houston   Los Angeles  New York   San Francisco  Seattle   Washington

Target: "Seattle"

The algorithm finds “Seattle” in just 3 checks, while a linear search could take up to 9 checks in the worst case.

Time complexity of binary search

• Time complexity (worst case): O(log n), where n is the number of elements in the list.
• Intuition: Each step halves the remaining search space, so after k steps you have at most n / 2^k elements left; solving n / 2^k = 1 gives k ≈ log₂ n.

Important requirement: The list must be sorted. If your data is unsorted and you cannot sort it, binary search is not appropriate.

Linear Search vs Binary Search: Side-by-Side Example

Now let’s see both algorithms in action on the same dataset and compare their performance.

Example: Search names with both algorithms

We will:

• Implement linear_search and binary_search.
• Create a list of names and a sorted version of that list.
• Search for the same name using both algorithms.
• Measure the time taken by each approach.

import time

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

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

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

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

    return -1


# Example usage
names = ["John", "Emily", "Michael", "Emma", "William",
         "Olivia", "James", "Sophia", "Benjamin", "Isabella"]

sorted_names = sorted(names)
target_name = "Sophia"

# Linear search
start_time = time.time()
linear_result = linear_search(names, target_name)
linear_time = time.time() - start_time

if linear_result != -1:
    print(f"Linear Search: {target_name} found at index {linear_result}")
else:
    print(f"Linear Search: {target_name} not found in the list")

print(f"Linear Search Time: {linear_time:.6f} seconds")
print()

# Binary search
start_time = time.time()
binary_result = binary_search(sorted_names, target_name)
binary_time = time.time() - start_time

if binary_result != -1:
    print(f"Binary Search: {target_name} found at index {binary_result}")
else:
    print(f"Binary Search: {target_name} not found in the list")

print(f"Binary Search Time: {binary_time:.6f} seconds")

Example output for a small list:

Linear Search: Sophia found at index 7
Linear Search Time: 0.000005 seconds

Binary Search: Sophia found at index 8
Binary Search Time: 0.000003 seconds

You can see the output in the screenshot below.

On such a small list, both are extremely fast, but as data size grows, binary search starts to win clearly.

Advanced Example: Performance on Large Lists

To really see the difference between O(n) and O(log n), let’s test both algorithms on a list of 1,000,000 integers.

import time

def linear_search(arr, target):
    for i, value in enumerate(arr):
        if value == target:
            return i
    return -1

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

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

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

    return -1


# create a large sorted list of integers
size = 1_000_000
data = list(range(size))
target = size - 1  # worst-case for linear search

# linear search
start = time.time()
linear_result = linear_search(data, target)
linear_time = time.time() - start

# binary search
start = time.time()
binary_result = binary_search(data, target)
binary_time = time.time() - start

print(f"Linear search index: {linear_result}, time: {linear_time:.6f}s")
print(f"Binary search index: {binary_result}, time: {binary_time:.6f}s")

Interpreting the results:

• Linear search may take noticeable time because it has to scan through many elements.
• Binary search will typically return much faster because it only needs around log₂(1,000,000) ≈ 20 comparisons.

This kind of real measurement shows why algorithm choice matters in practice.

Comparison Table: Linear Search vs Binary Search

Here is a clear summary of the key differences.

When to Use Which in Real Projects

Use linear search when:

• Your list is small (for example, tens or a few hundred elements).
• The data is unsorted, and you only run a search occasionally.
• Code simplicity is more important than performance.

Use binary search when:

• Your list is large (thousands, millions of elements).
• You can keep the list sorted or are already working with sorted data.
• You perform many search operations and need them to be fast.

In many real projects, we first write simple linear searches to keep the code easy to understand. When performance becomes a problem (for example, when processing logs, large CSV files, or user records), we refactor the data structure (sort it, or use something like a set or dictionary) and switch to a faster lookup approach like binary search or hash-based structures.

Common Mistakes (and How to Avoid Them)

With linear search:

• Forgetting to return -1 when the item is not found.
• Modifying the list inside the loop by mistake.

With binary search:

• Trying to use it on an unsorted list.
• Off-by-one errors in low, high, and mid.
• Using normal division / instead of integer division // when calculating the middle index.

Buggy example (wrong mid calculation):

mid = (low + high) / 2   # Bad: this is a float!

Correct version:

mid = (low + high) // 2  # Good: integer index

Practice Exercises

If you want to go from beginner to interview-ready, try these short exercises:

1. Modify linear_search to return all indices of the target value instead of just the first one.
2. Implement a recursive version of binary_search.
3. Change the binary_search function to return a boolean (True or False) instead of an index.
4. Think about what happens if the list contains duplicate values. Which index will binary search return?

FAQ: Linear vs Binary Search in Python

You may also like to read:

• Read a Specific Line from a Text File in Python
• Read the Last Line of a File in Python
• Write a Dictionary to a File in Python
• Replace a Specific Line in a File Using Python

Bijay Kumar

Bijay Kumar is an experienced Python and AI professional who enjoys helping developers learn modern technologies through practical tutorials and examples. His expertise includes Python development, Machine Learning, Artificial Intelligence, automation, and data analysis using libraries like Pandas, NumPy, TensorFlow, Matplotlib, SciPy, and Scikit-Learn. At PythonGuides.com, he shares in-depth guides designed for both beginners and experienced developers. More about us.

enjoysharepoint.com/