Search Problems

The search problems are the problems of finding a particular item (the search "key") or set of items within a collection of items.

Linear search sequentially checks each element of the list for the target value until a match is found or until all the elements have been searched. Hence, in worst case, the algorithm has to check every element of the list.

use std::cmp::PartialEq;

fn linear_search<T: PartialEq>(item: &T, arr: &[T]) -> Option<usize> {
    for (i, data) in arr.iter().enumerate() {
        if item == data {
            return Some(i);
        }
    }

    None
}

fn main(){
    let arr = [81, 12, 32, 56, 17, 38, 19, 10];
    let result = linear_search(&17, &arr);
    println!("result is {result:?}");
}

Properties

  • Worst case performance: O(n)
  • Best case performance: O(1)
  • Average case performance: O(n)
  • Worst case space complexity: O(1) iterative

Binary search compares the target value to the middle element of a sorted array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array.

Binary search is also known as half-interval search or logarithmic search

Properties

  • Worst case performance O(log n)
  • Best case performance O(1)
  • Average case performance O(log n)
  • Worst case space complexity O(1)

Exponential search begins by searching a small range of elements, gradually increasing the range exponentially until the target is found or the entire list is searched.

Properties

  • Worst case performance O(log i)
  • Best case performance O(1)
  • Average case performance O(log i)
  • Worst case space complexity O(1)

Jump Search search a sorted array first checking all items L(km), where k ∈ N and m is the block size, until an item is found that is larger than the search key. To find the exact position of the search key in the list a linear search is performed on the sublist L[(k-1)m, km].

Properties

  • Worst case performance O(√n)
  • Best case performance O(1)
  • Average case performance O(√n)
  • Worst case space complexity O(1)

Unlike Binary search dividing array into two equal parts, Fibonacci search divides the sorted array into two parts that have sizes consecutive Fibonacci numbers to narrow down the possible location.

Properties

  • Worst case performance O(log n)
  • Best case performance O(1)
  • Average case performance O(log n)
  • Worst case space complexity O(1)