Linear Search And Binary Search In Python Program

In this Python tutorial, we will discuss, linear search and binary search in Python program. This tutorial will walk you through implementing two of the most fundamental search algorithms: linear search and binary search in Python. You will also learn to implement binary search without using functions.

Table of Contents

linear search and binary search in Python

Searching is a common operation in computer science, where you need to find a particular value from a collection of values. Two common algorithms for this operation are linear search and binary search.

Linear Search:

In linear search, you start from the first element and compare each element with the target value until you find a match.
Time Complexity: O(n)

How it works:

Start from the first element of the array.
Compare the target value with the current element.
If it matches, return the index.
If not, move to the next element.
Repeat steps 2-4 until you find the target or reach the end of the array.

Performance:

Time complexity is O(n) because, in the worst-case scenario, it checks each element in the array.
No requirement for the array to be sorted.

Binary Search:

In binary search, the array must be sorted. You repeatedly divide the array into halves until the value is found.
Time Complexity: O(log n)

How it works:

The array must be sorted before using binary search.
Start by setting two pointers, one at the start (left) and one at the end (right) of the array.
Find the middle element.
Compare the middle element with the target.
If it matches, return the index.
If the target is larger than the middle element, move the left pointer to the middle + 1.
If the target is smaller than the middle element, move the right pointer to the middle – 1.
Repeat steps 3-7 until you find the target or the pointers cross (left > right).

Performance:

Time complexity is O(log n) because it effectively halves the search space with each iteration.
Requires the array to be sorted.

Linear Search in Python

Implementing Linear Search

Here’s a step-by-step guide to implementing a linear search algorithm in Python:

def linear_search(arr, target):
    # Loop through each element in the array
    for index, element in enumerate(arr):
        # If the element matches the target, return the index
        if element == target:
            return index
    # If the loop finishes, the target was not found
    return -1

Example: Linear Search Program in Python

Let’s write a Python program for linear search to find the index of a target value in an array.

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

# Example array and target value
arr = [4, 2, 7, 1, 9, 3]
target = 7

# Call the linear_search function
index = linear_search(arr, target)

# Output the result
if index != -1:
    print(f"Element {target} found at index {index}")
else:
    print(f"Element {target} not found in the array")

You can see the output:

Binary Search in Python

Implementing Binary Search with a Function

Here’s a step-by-step guide to implementing binary search using a function:

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    # Continue the search while the left index is less than or equal to the right index
    while left <= right:
        mid = (left + right) // 2
        
        # Check if the target is present at mid
        if arr[mid] == target:
            return mid
        
        # If target is greater, ignore the left half
        elif arr[mid] < target:
            left = mid + 1
        
        # If target is smaller, ignore the right half
        else:
            right = mid - 1
    
    # If we reach here, the element was not present
    return -1

Example: Binary Search Program in Python

Let’s see a Python program to implement binary search using the above function.

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Example sorted array and target value
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 6

# Call the binary_search function
index = binary_search(arr, target)

# Output the result
if index != -1:
    print(f"Element {target} found at index {index}")
else:
    print(f"Element {target} not found in the array")

You can see the output like below:

linear and binary search program in python

Implement Binary Search Without a Function

Here’s how you can write a Python program to implement binary search without using a function.

Example: Binary Search in Python Without a Function

# Example sorted array and target value
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 6

# Set initial left and right indices
left, right = 0, len(arr) - 1

# Binary search without function
while left <= right:
    mid = (left + right) // 2
    
    # Check if target is present at mid
    if arr[mid] == target:
        print(f"Element {target} found at index {mid}")
        break
    
    # If target is greater, ignore the left half
    elif arr[mid] < target:
        left = mid + 1
    
    # If target is smaller, ignore the right half
    else:
        right = mid - 1
else:
    print(f"Element {target} not found in the array")

You can see the output below in the screenshot.

binary search in python without function

Linear Search and Binary Search in Python

Here is a comparison of Linear Search and Binary Search in Python in a tabular format:

Aspect	Linear Search	Binary Search
Algorithm Type	Sequential Search	Interval Search
How it works	Sequentially checks each element for a match	Repeatedly divides the search interval in half
Sorted Data Required	No, works on both sorted and unsorted arrays	Yes, only works on sorted arrays
Time Complexity	O(n)	O(log n)
Space Complexity	O(1)	O(1)
Implementation	Easier	Slightly more complex
Performance	Slower for large datasets	Faster for large datasets
Best-case Scenario	O(1), when the element is at the first position	O(1), when the element is at the middle position
Worst-case Scenario	O(n), when the element is at the last position or not present	O(log n)
Use Cases	Small datasets, unsorted data	Large datasets, sorted data

This table summarizes the key differences between linear search and binary search algorithms in Python.

Conclusion

This tutorial has covered how to implement linear search and binary search in Python, including examples with and without using functions. Whether you’re looking to write a python program to implement linear search and binary search, or specifically focusing on binary search in Python without using a function, this tutorial has you covered.