Searching Algorithms: Linear and Binary

A searching algorithm finds specific elements within a collection, like an array or list. Common methods include Linear Search, which checks each element, and Binary Search, which divides a sorted array to find the target. These algorithms are essential for quick data retrieval and manipulation in computer science.

Linear search

Linear search works by checking each element in a list one by one, starting from the first element and moving to the last. If it finds the target element, it stops and returns the position. If it doesn’t find the target, it concludes that the element is not in the list. Linear search is simple but can be slow for large lists since it may need to check every element.

Time complexity: O(n), Space complexity: O(1)

(Efficiency might be better in sorted data)

Linear search in Python

Steps:

1. Create a function that takes two params (array, value)

2. Loop through the array and check is the desired element is equal to any value

3. If it is, return the index at which the element is found

4. If the value is never found, return -1

def linearSearch(array, value): 
    for i in range(len(array): 
        if array[i] == value: 
            return i 
        else: 
            return -1
print(linearSearch([20,40,30,50], 50)

Time complexity: O(n), Space complexity: O(1)

Binary search

Binary search is an efficient algorithm used to find a target element in a sorted list.

• Binary search is faster than linear search

• Half of the remaining elements can be eliminated at a time, instead of eliminating them one by one

Binary search works by repeatedly dividing a sorted list in half to find a target element. Here's how it works:

1. Start with the middle element: Compare the target with the middle element of the list.

2. Narrow the search:

   • If the target is equal to the middle element, you've found it.

   • If the target is smaller, search the left half of the list.

   • If the target is larger, search the right half of the list.

3. Repeat: Continue dividing the list until the target is found or the list can't be divided further (meaning the target isn't in the list).

Binary search is much faster than linear search, with a time complexity of O(log n).

Binary search in Python

Steps:

1. Create function with two params(sorted array, value)

2. Create two pointers : a left pointer at the start of the array and a right pointer at the end of the array

3. Based on left and right pointers calculate middle pointer

4. While middle is not equal to the value and start <= end loop:

   • if the middle is greater than the value move the right pointer down

   • If the middle is less than the value, move the left pointer op

5. If the value is never found return -1

import math 
def binarySearch(array, value): 
    start = 0
    end = len(array) -1 
    middle = math.floor((start+end)/2))
    print(start, middle, end)
    while not(array[middle] == value) and start <= end: 
        if value < array[middle]:
            end = middle -1 
        else: 
            start = middle + 1 
        middle = math.floor((start+end)/2))
        # print(start, middle, end)
    if array[middle] == value:
        return middle
    else: 
        return -1

custArray = [8,9,10,11,12,13,14]
print(binarySearch(custArray, 14))

The complexity of Binary search

The time complexity of binary search is:

• Best Case: O(1) (when the middle element is the target)

• Average and Worst Case: O(log n) (as the list is halved with each step)

The space complexity of binary search is:

• O(1) for the iterative version, as it only uses a few additional variables.

• O(log n) for the recursive version, due to the call stack.

End