Searching algorithms

A search algorithm is a core concept in computer science. As the name states the algorithm solves a search problem by retrieving information stored in a data structure. Not only does choosing and implementing the right search algorithm increase efficiency of the result, but also has a noticeable impact on performance.

In this topic we are going to have a glimpse on the following: Linear search, Binary search, Jump search, Interpolation search, Exponential search and lastly Fibonacci search. As well as highlight instances where it is better to use a particular search algorithm. Let us first look into how they work.

Brief descriptions and code

Linear search (or sequential search)

This simple algorithm is used for searching an element with a specific value in the array. The algorithm checks each array element until it finds the target value or reaches the array end.

function found_value(array, value):

    for index in [1, len(array)]:

        if array[index] == value then:
            return index

    return -1 

Binary search

This algorithm searches for the target value in a sorted array, it follows the divide-and-conquer principle. It starts by comparing the middle array element and in a result of a math, returns the element index. Otherwise, the search proceeds to the left or right subarray, depending on whether the target value is lesser or greater than the middle element. It goes on until it finds the target value or a new search interval is empty .

function found_binary(array, value):
    left = 1
    right = len(array)

    while left <= right:
        middle = int((left+right)/2)

        if array[middle] == value then:
            return middle

        elif array[middle] > value then:
            right = middle - 1
  
        else:
            left = middle + 1
            
    return -1  

Jump search

This algorithm works by dividing a sorted array into smaller blocks and then performing a linear search within the relevant block looking for where a target element might be. The essence of the algorithm lies in jumping over blocks to locate the block that might contain the target element efficiently.

function jump_search(array, value):

    if array.isEmpty() then:
        return -1
    
    curr = 1
    prev = 1
    last = len(array)
    step = floor(sqrt(last))

    while array[curr] < value:
        if curr == last then:
            return -1
        prev = curr
        curr = min(curr + step, last)

    while array[curr] > value:
        curr = curr - 1
        if curr <= prev then:
            return -1

    if array[curr] == value:
        return curr

    return -1 

Interpolation search

This algorithm's concept is to calculate a probable position of the target based on its value and the distribution of values in the data set. The position is calculated using a formula, which takes the the value range. The algorithm then adjusts the search range based on whether the target is less than or greater than the value at the calculated position.

function interpolation_search(array, value)
    low = 0
    high = len(array) - 1
    
    while low <= high and array[low] <= value and array[high] >= value do:
        position = low + ((value - array[low]) * (high - low)) / (array[high] - array[low])
        
        if array[position] == value then:
            return position
        
        if array[position] < value then:
            low = position + 1

        else
            high = position - 1
    
    return -1

Exponential search (or galloping search, or Struzik search)

This algorithm is used to search sorted, unbounded/infinite arrays and features two fundamental steps: finds the range where the element is present and then perform a binary search in the found range to find the target.

function exponential_search(array, value):
    n = len(array)
    
    if array[0] == value then:
        return 0
    
    i = 1

    while i < n and array[i] <= value do:
        i = i * 2
    
    return binary_search(array, value, i / 2, min(i, n - 1))
    
binary_search(array, value, low, high):
    while low <= high do
        mid = (low + high) / 2
        
        if array[mid] == value then:
            return mid
        
        else if array[mid] < value then:
            low = mid + 1
        
        else
            high = mid - 1
    
    return -1

Fibonacci search

This algorithm uses a similar approach as the binary search algorithm to narrow down the possible location of the target element, but with the help of Fibonacci numbers. The array is divided into two parts that are the size of consecutive Fibonacci numbers (unlike two equal sizes in binary search), then narrows down the search range based on the comparison of the target value with the middle element of the current subarray.

funtion fibonacci_search(array, value):
    n = length of array
    
    fibM_minus_2 = 0
    fibM_minus_1 = 1
    fibM = fibM_minus_1 + fibM_minus_2
    
    while fibM < n do
        fibM_minus_2 = fibM_minus_1
        fibM_minus_1 = fibM
        fibM = fibM_minus_1 + fibM_minus_2
    
    offset = -1
    
    while fibM > 1 do
        i = min(offset + fibM_minus_2, n - 1)
        
        if array[i] < value then:
            fibM = fibM_minus_1
            fibM_minus_1 = fibM_minus_2
            fibM_minus_2 = fibM - fibM_minus_1
            offset = i
        
        else if array[i] > value then:
            fibM = fibM_minus_2
            fibM_minus_1 = fibM_minus_1 - fibM_minus_2
            fibM_minus_2 = fibM - fibM_minus_1
        
        else
            return i
    
    if fibM_minus_1 = 1 and array[offset + 1] = value then:
        return offset + 1
    
    return -1

Comparison of searching algorithms

When to use each algorithm

• Linear search: Despite being one of the simplest search algorithms to understand and implement, Linear Search is generally not used in practice due to its poor performance with larger data sets. Yet it is useful if a data set is not sorted at all and the algorithm itself requires minimal additional memory.
• Binary search: One of the simpler and most efficient algorithms in most situations, only requiring a sorted data set. Yet its drawbacks are additional memory, especially if the algorithm has to jump more times backwards.
• Jump search: Quite an efficient algorithm, just like binary search requires a sorted data set. The difference is that this algorithm proves useful, when jumping backwards takes more time than jumping forward.
• Interpolation search: More efficient than linear search for larger as well as unsorted data sets. The efficiency is determined by the block size and fixed interpolation size. A major drawback is if the data set is not uniformly distributed.
• Exponential search: Can be used with unbounded or infinite lists, being more efficient than linear search. Sorting such data sets might not always be possible as well as determining the optimal interval size might prove difficult, decreasing the efficiency.
• Fibonacci search: Similar to binary search, yet a more complicated implementation. Due to Fibonacci search algorithm using addition and subtraction unlike binary search, where multiplication and division operations take place, it requires less resources. Furthermore, in the case of random-access memory, this algorithm can reduce the searching time.

Conclusion

Search algorithms are a crucial aspect in computer science. By understanding the strengths and weaknesses of each algorithm, you can make informed decisions and get the best results/performance in a particular situation. This guide provides you with just a starting point, but the best way to truly understand these algorithms is to implement them yourself. Happy coding!