Searching Algorithms

A bunch of searching algorithms on arrays 🔎.

Linear Search

Rust

#![allow(unused)]
fn main() {
pub fn linear_search<T: Eq>(array: &[T], value: T) -> Option<usize> {
    array
        .iter()
        .enumerate()
        .find_map(|(i, v)| if *v == value { Some(i) } else { None })
}
}

Java

    public static <T> Optional<Integer> search(T[] array, T toFind) {
        for (var index = 0; index < array.length; index++)
            if (array[index] == toFind)
                return Optional.of(index);

        return Optional.empty();
    }

Binary Search

In the course, you will study the recursive implementation of the binary search, in my code, I've written an iterative one (I don't "like" recurion)

Rust

#![allow(unused)]
fn main() {
pub fn binary_search<T: Ord>(array: &[T], value: T) -> Option<usize> {
    let mut step = array.len();
    let mut index = 0;

    while step > 0 {
        let next = index + step;

        while next < array.len() {
            let cmp = match array.get(next) {
                Some(v) => v.cmp(&value),
                None => break,
            };

            match cmp {
                Equal => return Some(next),
                Less => index = next,
                Greater => break,
            }
        }

        step /= 2;
    }

    None
}
}

Java

    public static <T extends Comparable<? super T>> Optional<Integer> binarySearch(T[] array, T toFind) {
        int jump = array.length - 1, index = 0;

        while (jump > 0) {
            while (index + jump < array.length) {
                var comparison = array[index + jump].compareTo(toFind);

                if (comparison > 0)
                    break;

                index += jump;

                if (comparison == 0)
                    return Optional.of(index);
            }

            jump /= 2;
        }

        return Optional.empty();
    }

Exercise

Given $A$, an array of integers, and two values $a$ and $b$, with $a\le b$, count how many elements of $A$ are included in the range $[a,b]$

The simplest way to solve the problem is to implement two functions: lower_bound and upper_bound, which are basically binary searches that don't stop once they find the value in the array. In the case of lower_bound, it finds the index of "the smallest value bigger or equal to $x$", and the upper_bound is "the biggest value smaller or equal to $x$" with $x$ being the value to find.

This way, we can find the upper_bound of $b$, and the lower_bound of $a$, and do a subtraction of the two to find the number of elements inbetween. There are a few corner cases to consider both for upper_bound, lower_bound and count_in_range (the function that solves the exercise) for which we return 0 (open an ISSUE if you want me to discuss them).

Rust

#![allow(unused)]
fn main() {
pub fn upper_bound<T: Ord>(array: &Vec<T>, value: T) -> Option<usize> {
    let mut step = array.len();
    let mut index = 0;

    if array.first().unwrap() > &value {
        return None;
    }

    while step > 0 {
        let next = index + step;

        while next < array.len() {
            let cmp = match array.get(next) {
                Some(v) => v.cmp(&value),
                None => break,
            };

            match cmp {
                Greater => break,
                _ => index = next,
            }
        }

        step /= 2;
    }

    Some(index)
}
}

#![allow(unused)]
fn main() {
pub fn lower_bound<T: Ord>(vector: &Vec<T>, value: T) -> Option<usize> {
    let mut step = vector.len();
    let mut index = vector.len() - 1;

    if vector.last().unwrap() < &value {
        return None;
    }

    while step > 0 {
        while step <= index {
            let cmp = match vector.get(index - step) {
                Some(v) => v.cmp(&value),
                None => break,
            };

            match cmp {
                Less => break,
                _ => index -= step,
            }
        }

        step /= 2;
    }

    Some(index)
}
}

#![allow(unused)]
fn main() {
    pub fn count_in_range<T: Ord>(vector: Vec<T>, lower: T, upper: T) -> usize {
        let lower = lower_bound(&vector, lower);
        let upper = upper_bound(&vector, upper);

        if let (Some(l), Some(u)) = (lower, upper) {
            return match l.cmp(&u) {
                Greater => 0,
                _ => u.abs_diff(l) + 1,
            };
        }

        0
    }
}

Java

TODO: make bound functions return Optional, handle corner cases

    public static <T extends Comparable<? super T>> Integer upperBound(List<T> list, T toFind) {
        int jump = list.size() - 1, index = 0;

        while (jump > 0) {
            while (index + jump < list.size() && list.get(index + jump).compareTo(toFind) <= 0)
                index += jump;

            jump /= 2;
        }

        return index;
    }

    public static <T extends Comparable<? super T>> Integer lowerBound(List<T> list, T toFind) {
        int jump = list.size() - 1, index = list.size() - 1;

        while (jump > 0) {
            while (index - jump >= 0 && list.get(index - jump).compareTo(toFind) >= 0)
                index -= jump;

            jump /= 2;
        }

        return index;
    }

TODO: write a countInRange method