Searching Algorithms

Introduction

Searching algorithms are crucial for finding specific elements in a data structure efficiently. This lesson covers some important searching algorithms, including their properties, time complexities, and implementations in Rust.

Key Points

  • Searching Algorithms: Techniques for finding an element in a data structure.
  • Time Complexity: A measure of the amount of time an algorithm takes to find an element based on the size of the input.

Linear Search is a simple algorithm that checks each element in a list sequentially until the target element is found or the end of the list is reached.

Linear Search Implementation

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

fn main() {
    let array = [10, 20, 30, 40, 50];
    let target = 30;
    match linear_search(&array, target) {
        Some(index) => println!("Found {} at index {}", target, index),
        None => println!("{} not found in the array", target),
    }
}

Code Explanation

  • linear_search: Iterates through the array and returns the index of the target element if found; otherwise, returns None.
  • Time Complexity: O(n) for all cases.

Binary Search is an efficient algorithm for finding an element in a sorted array by repeatedly dividing the search interval in half.

Binary Search Implementation

fn binary_search<T: Ord>(arr: &[T], target: T) -> Option<usize> {
    let mut low = 0;
    let mut high = arr.len() as isize - 1;

    while low <= high {
        let mid = (low + high) / 2;
        match arr[mid as usize].cmp(&target) {
            std::cmp::Ordering::Less => low = mid + 1,
            std::cmp::Ordering::Greater => high = mid - 1,
            std::cmp::Ordering::Equal => return Some(mid as usize),
        }
    }
    None
}

fn main() {
    let array = [10, 20, 30, 40, 50];
    let target = 30;
    match binary_search(&array, target) {
        Some(index) => println!("Found {} at index {}", target, index),
        None => println!("{} not found in the array", target),
    }
}

Code Explanation

  • binary_search: Repeatedly divides the search interval in half to locate the target element.
  • Time Complexity: O(log n) for all cases.

Interpolation Search is an improved version of Binary Search for uniformly distributed data. It estimates the position of the target element based on its value.

Interpolation Search Implementation

fn interpolation_search<T: Ord>(arr: &[T], target: T) -> Option<usize> {
    let mut low = 0;
    let mut high = arr.len() as isize - 1;

    while low <= high && arr[low as usize] <= target && arr[high as usize] >= target {
        if low == high {
            return if arr[low as usize] == target {
                Some(low as usize)
            } else {
                None
            };
        }

        let pos = low + (((target as usize - arr[low as usize] as usize) * (high - low)) / (arr[high as usize] as usize - arr[low as usize] as usize)) as isize;

        match arr[pos as usize].cmp(&target) {
            std::cmp::Ordering::Less => low = pos + 1,
            std::cmp::Ordering::Greater => high = pos - 1,
            std::cmp::Ordering::Equal => return Some(pos as usize),
        }
    }
    None
}

fn main() {
    let array = [10, 20, 30, 40, 50];
    let target = 30;
    match interpolation_search(&array, target) {
        Some(index) => println!("Found {} at index {}", target, index),
        None => println!("{} not found in the array", target),
    }
}

Code Explanation

  • interpolation_search: Estimates the position of the target based on its value relative to the values at the boundaries.
  • Time Complexity: O(log log n) for uniformly distributed data; O(n) in the worst case.

Jump Search is an algorithm that works on sorted arrays by jumping ahead by a fixed number of elements and performing a linear search within the block where the target might be found.

Jump Search Implementation

fn jump_search<T: Ord>(arr: &[T], target: T) -> Option<usize> {
    let length = arr.len();
    let jump = (length as f64).sqrt() as usize;
    let mut prev = 0;
    let mut curr = 0;

    while curr < length && arr[curr] < target {
        prev = curr;
        curr = (curr + jump).min(length - 1);
    }

    for i in prev..=curr {
        if arr[i] == target {
            return Some(i);
        }
    }
    None
}

fn main() {
    let array = [10, 20, 30, 40, 50];
    let target = 30;
    match jump_search(&array, target) {
        Some(index) => println!("Found {} at index {}", target, index),
        None => println!("{} not found in the array", target),
    }
}

Code Explanation

  • jump_search: Jumps ahead by a fixed number of steps and performs a linear search within the current block.
  • Time Complexity: O(√n) for all cases.

Real World Examples

Linear Search

  • Small or Unsorted Data: Useful for simple cases where the data size is small or the data is not sorted.

Binary Search

  • Sorted Data: Efficient for searching in sorted datasets such as in a database index or when using sorted lists.

Interpolation Search

  • Uniformly Distributed Data: Useful for datasets where elements are uniformly distributed, such as numerical ranges.

Jump Search

  • Sorted Data with Large Gaps: Effective for large datasets where you want a balance between linear search and binary search.

Conclusion

Searching algorithms are essential for finding elements in various data structures efficiently. Understanding and implementing these algorithms in Rust helps you solve searching problems effectively and grasp fundamental computer science concepts.