Photo by Dmitry Chernyshov on Unsplash

Learning Search Algorithms

Searching a page on the web or retrieving a record from a database, searching algorithms are a helpful tool to use.

Search algorithms are the best tool to retrieve pieces of information from a data structure. Searching algorithms are classified based on their mechanism of searching style. We can classify them into two categories:

1. Sequential Search: Sequential Search algorithms are those who sequentially search a data structure, like linear Search
2. Interval Search: We use interval search algorithms in sorted data structures. Comparision to linear searching these types of algorithms are more efficient and fast. An example of this type of search algorithm is Binary Search. Binary Search is also called half interval search because it divides the list into two-part after every step.

So, let’s check how to use Linear Search and Binary Search to search an element from an array.

1. Linear Search

Linear Search sequentially searches an array. It means Linear Search compares every element with the data, and after finding it returns that information.

A linear search starts from index 0 and compares every element of the array, and if it finds that elements, then it returns the index of that element in that array, and if it’s finds nothing, then we can set to None or null.

And if we talk about the time complexity of the Linear Search, then it’s O(n) in the worst case when we have to compare all elements of the array, O(1) in the best case if the element is available on the 0th index of the array.

So let’s see how it works with the help of a program.

def linear_search(arr, elem):
    for i in range(len(arr)):
        if arr[i] == elem:
            return i
    return Nonearr = [13, 23, 12, 34, 13]
elem = int(input("element: "))
result = linear_search(arr, elem)
if result == None:
    print("element not found");
else:
    print(f"element found at index {result}")

In the above example, we have implemented linear Search using Python.

So let’s break the code. At first, we created a function linear_search that accepts two arguments, the first one is an array and the second one is the element that we want to search.

Then it will loop through every element in the array, starting from index 0 to n-1, where n is the length of the array. And if it finds the item, then it will return the index of the element and will exit from the loop and function. If it doesn’t find anything, then it will return None.

2. Binary Search

Binary Search suitable for a sorted array. Binary Search is faster and more efficient than Linear Search. Binary Search divide range in half after every step. The time complexity for a Binary Search algorithm in the worst case is O(log n).

So, let’s see how it works:

def binary_search(arr, low, high, elem):
    while low <= high:
        mid = low + (high - low) // 2if arr[mid] == elem:
            return mid
        elif arr[mid] < elem:
            low = mid + 1
        else:
            high = mid - 1
    return Nonearr = [12, 24, 34, 110, 145, 240]
elem = int(input("elem: "))
result = binary_search(arr, 0, len(arr) - 1, elem)
if result == None:
    print("element not found");
else:
    print(f"element found at index {result}")

In the above code, low is the lowest index, and high is the highest index of the array. In Binary Search, we compare the element that we want to search with the middle element if it matches then we return the central index.

If the element is bigger than the central element, then we set the index next to the middle to low and use the right array and also discard the other half. If the element is lower than the middle element, then set the middle-1 index to high and calculate the mid again.

It continues until the highest index becomes lower than the lowest index. And if it doesn’t find anything, then it will return None.