Difference Between Linear Search And Binary Search In Python

In this tutorial, I will explain the key differences between linear search and binary search algorithms in Python. As a software engineer working on various projects, I’ve encountered situations where choosing the right search algorithm can significantly impact the performance and efficiency of my code. In this article, I will explain everything about linear search and binary search in Python with examples.

Table of Contents

Linear Search in Python

Linear search, also known as sequential search, is a simple searching algorithm that traverses an array or list sequentially from the beginning to find a specific element. It checks each element one by one until the target element is found or the end of the array is reached.

Here’s an example of how linear search works in Python:

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

Now, let me show you an example.

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")

In this example, we have a list of names, and we want to find the index of “Emma” using linear search. The algorithm starts from the beginning of the list and compares each name with the target name until a match is found or the end of the list is reached.

Here is the complete code:

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

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")

I executed the above Python code, and you can see the exact output in the screenshot below:

difference between linear search and binary search

Time Complexity of Linear Search

The time complexity of linear search is O(n), where n is the number of elements in the array. In the worst case, when the target element is not present in the array or is located at the last position, the algorithm needs to traverse the entire array, resulting in a linear time complexity.

Read How to catch multiple exceptions in Python?

Binary search in Python

Binary search is an efficient searching algorithm that works on sorted arrays. It follows a divide-and-conquer approach to find the target element by repeatedly dividing the search interval in half.

Here’s an example of how binary search works:

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

Now, let me show you a complete example of how it works:

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
cities = ["Atlanta", "Boston", "Chicago", "Denver", "Houston", "Los Angeles", "New York", "San Francisco", "Seattle", "Washington"]
target_city = "Houston"

# Perform binary search
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

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

Here is the output in the screenshot below:

Time Complexity of Binary Search

The time complexity of binary search is O(log n), where n is the number of elements in the array. Each iteration halves the search interval, resulting in a logarithmic time complexity. This makes binary search much faster than linear search, especially for large sorted arrays.

Read Complex Numbers in Python

Linear Search and Binary Search – Complete Example

Let me show you an example that includes both linear search and binary search in Python, along with a comparison of their performance:

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")

In this example, we have a list of names that we want to search for a specific name. We perform both linear search and binary search and compare their results and execution time.

We define the linear_search function that takes an array arr and a target element target as input. It iterates through the array sequentially and returns the index of the target element if found, or -1 if not found.
We define the binary_search function that takes a sorted array arr and a target element target as input. It uses the binary search algorithm to find the index of the target element by repeatedly dividing the search space in half. It returns the index of the target element if found, or -1 if not found.
We create a list of names and a sorted version of the list using the sorted function.
We specify the target name we want to search for.
For linear search, we measure the execution time using time.time() before and after calling the linear_search function. We then print the result and the execution time.
For binary search, we measure the execution time using time.time() before and after calling the binary_search function with the sorted list of names. We then print the result and the execution time.

Output:

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

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

In this example, both linear search and binary search correctly find the target name “Sophia” at index 7. However, binary search typically has a faster execution time compared to linear search, especially for larger datasets, due to its logarithmic time complexity.

Read How to reverse a number in Python

Differences between Linear Search and Binary Search

Linear Search	Binary Search
Searches sequentially from the beginning	Searches by dividing the array in half
Works on both sorted and unsorted arrays	Works only on sorted arrays
Time complexity: O(n)	Time complexity: O(log n)
Easier to implement	Requires more complex implementation
Suitable for small arrays or unsorted data	Suitable for large sorted arrays

Conclusion

In this tutorial, we explored the differences between linear search and binary search algorithms in Python. I explained how the linear search works on both sorted and unsorted arrays, while binary search requires a sorted array. Linear search has a time complexity of O(n), making it suitable for small arrays or unsorted data. Binary search, with its O(log n) time complexity, is more efficient for large sorted arrays. Do let me know in the comment below if this works for you.