Search algorithms.

• Isaac Tonyloi

Search algorithms are some of the most popular algorithms that we use in our everyday lives. There are two types of search algorithms:

• Linear search

• Binary search

Linear Search.

One of the simplest search algorithms. Linear search algorithms are sequential algorithms which involve traversing of a sequence of values such as a list or an array, from the beginning to the end until a match has been found or to the end of the list. If the search is successful i.e if the element is located the algorithm will return the index of the element, however if the element cannot be located the algorithm will return -1.

Characteristics of the Linear Search Algorithms.

The linear search algorithm can be applied to both sorted and unsorted lists.
Linear search algorithms have a time complexity of O(N) which implies that time is linearly dependent on the size of the array/list.
Very simple to implement.

Implementation of the Linear Search Algorithm.

def linear_search(array, x, n):
    for i in range(0, n):
        if array[i] == x:
            return i
    return -1

#implementation
array =[23, 45, 12, 90, 34, 7]
x = 34
n = len(array)

result = linear_search(array, x, n)

if result == -1:
    print("Element is not present in the array!")

else:
    print("Element is present in the array !")

Output:

Element is present in the array !

Binary Search

Unlike Linear Search algorithm the Binary search algorithm can only be used if the elements of a list or array are sorted.

Steps Involved in Binary Search.

• Step 1. We first need to determine if the elements of that list are sorted.

• Step 2. If so compare the element with the element in the middle of the array/list

• Step 3. If the element matches with the elements in the middle of the array/list return the index of the element.

• Step 4. Otherwise determine if the element you’re searching for is greater or less than the element in the middle of the list/array.

• Step 5. if the element is greater than the element in the middle of the list/array pick the elements to the right and start from step 1 again.

• Step 6. If the element to be searched is less than the element of in the middle of the elements to the left pick element on the left and begin again from step 1.

Unlike the Linear search algorithm the binary search algorithm is very useful in cases where Lists/ arrays contain very large elements. However, the list/array in question needs to be sorted beforehand.

Features of the Binary Search Algorithm.

It is particularly good for searching through very large lists/arrays.
It has a time complexity of O(Log N).
The Binary search can be Implemented in two ways:

• Iterative Method.

• Recursive Method.
  The recursive method of implementing the binary search follows the divide and conquer approach while the iterative method doesn’t. Both of these methods can be implemented as shown below.

Iterative Implementation of the Binary Search.

def binary_search(array, x, low, high):
    while low <= high:
        mid = low + (high - low)//2
        if array[mid] == x:
            return mid
        elif array[mid] < x:
            low = mid +1
        else:
            high = mid -1
    return -1

#implementation of the algorithm
array = [12, 13, 15, 17, 28, 88, 90, 99]
x = 28
index = binary_search(array, x, 0, len(array)-1)
if index != -1:
    print("Element can be found at Index: " +str(index))
else:
    print("Element cannot be found !")

Output:

Element can be found at Index: 4

Recursive Implementation of the Binary Search Algorithm.

def binary_search(array, x, low, high):
    if high >= low:
        mid = low + (high - low)//2
        if array[mid] == x:
            return mid
        elif array[mid] > x:
            return binary_search(array, x, low,  mid-1)
        else:
            return binary_search(array, x, mid + 1, high)

    return -1

#implementation of the algorithm
array = [12, 67, 77, 79, 88, 90]
x = 79
result_index = binary_search(array, x, 0, len(array)-1)
if result_index != -1:
    print("The element in the array can be found at index: " +str(result_index))
else:
    print("Element cannot be found in the array !")

Output:

The element in the array can be found at index: 3