Searching Algorithms in Python

Searching algorithms are implemented to search for elements and retrieve their values from any data structure. Based on the search operation, searching algorithms can be classified into two categories:

• Sequential Search Algorithm: In a sequential search algorithm, each element of the list is traversed and checked. For example, Linear Search.
• Interval Search Algorithm: In an interval search algorithm, search is performed on a sorted data structure. These algorithms are much more efficient as they divide the search space in half subsequently. For example, Binary search.

A sorting algorithm can be judged based on the following criteria:

• Completeness
• Optimality
• Search Complexity
• Time Complexity

Linear Search

Linear search is a simple searching algorithm wherein each data element in a list is traversed and checked. If the element to be searched is found, we return its value. Otherwise, an error message is displayed. Linear search is a type of sequential search.

Implementation of Linear Search

The linear search algorithm is based on the following steps:

• We iterate over the given list and compare each value with the value to be searched.
• If a match is found, we return the index position of that element in the list.
• Otherwise, we return -1 to indicate that the element does not exist in the given list.

#Function to implement Linear Search
def linearSearch(tempList, value):
    for i in range(len(tempList)):
        if tempList[i] == value:
            return i
    return -1

print(linearSearch([20,40,30,50,90], 50))

#Output
3

Time and Space Complexity

The time complexity for the linear search algorithm is O(N) as we iterate over the entire list to search for the given element. The space complexity is O(1) as no additional memory is required.

Binary Search

Binary search is a searching algorithm wherein elements are searched from a sorted list or array. Binary search is an interval search algorithm. In the implementation of the algorithm, the list is broken down into halves based on the values of the elements. Then, the same process is repeated on the sub-lists and searched further till the required element is found.

Implementation of Binary Search

• We are given a list of sorted elements and let the element to be searched be value.

• Set two pointers start and end at the lowest and the highest positions respectively.

• Find the middle value of the list((start+end)/2).

• If value is greater than middle set the pointers to the right of middle, creating a new sub-list. Otherwise, move to the left and create the new seub-list.

• Keep comparing the middle value to the value to be searched until the given element is found.

#Function to implement Binary Search
import math
def binarySearch(tempList, value):
    start = 0
    end = len(tempList)-1
    middle = math.floor((start+end)/2)
    while not(tempList[middle]==value) and start<=end:
        if value < tempList[middle]:
            end = middle - 1
        else:
            start = middle + 1 
        middle = math.floor((start+end)/2)
        # print(start, middle, end)
    if tempList[middle] == value:
        return middle
    else:
        return -1
        
searchList = [8, 9, 12, 15, 17, 19, 20, 21, 28]
print(binarySearch(searchList, 15))

#Output
3

Time and Space Complexity

The time complexity for binary search is O(logN) because the list is continuously divided into halves and elements of the sub-lists are searched further. The space complexity is O(1) as no additional memory is required.