Python : Linear search and Binary Search

Practicing Python From Basics

Linear Search:

• Linear search, also known as sequential search, checks each element in a collection one by one until the target element is found or the end of the collection is reached.
• It's a simple but inefficient algorithm, especially for large datasets, as it has a time complexity of O(n) in the worst case.
• Linear search is applicable to both sorted and unsorted collections.

Implementation

def linear_search(key,arr):
    for index in range(len(arr)):
        if arr[index] == key:
            return index

    return 0

Calling function

arr = [5,8,2,10,3,6]
key = 3
result = linear_search(key,arr)

if result:
    print(f'Element {key} found at index {result}')

else:
    print("Element not found")

Element 3 found at index 4

2nd calling

key1 = 7
result1 = linear_search(key1,arr)

if result1:
    print(f'Element {key1} found at index {result1}')

else:
    print("Element not found")

Element not found

• The linear_search function takes a list arr and a target value key.
• It iterates through each element of the list using a for loop.
• For each element, it checks if it matches the target value.
• If a match is found, it returns the index of the element. If not found, it returns 0.

Binary Search

• Binary search is a more efficient algorithm for finding a target value within a sorted array.
• It repeatedly divides the search interval in half until the target is found or the interval is empty.
• Binary search has a time complexity of O(log n), making it significantly faster than linear search for large datasets.
• It requires the array to be sorted beforehand.

Implementation

def binary_search(key,arr):
    start, end = 0, len(arr)-1

    while start<=end:
        mid = (start+end)//2

        if arr[mid] == key:
            return mid

        elif arr[mid]<key:
            start = mid+1

        else:
            end = mid-1

    return 0

Calling Binary search

arr = [2, 4, 6, 8, 10, 12, 14, 16]
key = 12
result = binary_search(key,arr)

if result:
    print(f'Element {key} found at index {result}')

else:
    print("Element not found")

Element 12 found at index 5

2nd Calling

key = 1
result = binary_search(key,arr)

if result:
    print(f'Element {key} found at index {result}')

else:
    print("Element not found")

Element not found

• The binary_search function takes a sorted array arr and a target value key.
• It initializes start and end pointers to the start and end of the array, respectively.
• It repeatedly calculates the mid index and compares the element at mid with the key.
• Based on the comparison, it updates start or end pointers to narrow down the search interval.
• It continues until the target is found or the search interval is empty, returning the index of the target or 0 if not found.