Function rudac::algo::search::fibonacci_search_with

pub fn fibonacci_search_with<T, F>(
    slice: &[T], 
    item: &T, 
    compare: &F
) -> Option<usize> where
    F: Fn(&T, &T) -> Ordering, 

Fibonacci search is a search algorithm that finds the position of a target value within a sorted array. Returns index of the found item, None otherwise

It has the advantage that one only needs addition and subtraction to calculate the indices of the accessed array elements, while classical binary search needs bit-shift, division or multiplication

Arguments

• slice: slice of ordered data
• item: item to be searched for
• compare: custom comparison closure

Examples

use rudac::algo::search::fibonacci_search_with;

// consider a vector of 2d points
let mut vec = vec![(3,1), (4,2), (5,3), (3,4), (10,5), (2,6), (6,7), (9,8), (8,9), (1,10)];
 
let compare = |x1: &(usize, usize),x2: &(usize, usize)| {x1.1.cmp(&x2.1)};
assert_eq!(vec[fibonacci_search_with(&vec, &(3,1), &compare).unwrap()], (3,1));
assert_eq!(vec[fibonacci_search_with(&vec, &(4,2), &compare).unwrap()], (4,2));
assert_eq!(vec[fibonacci_search_with(&vec, &(5,3), &compare).unwrap()], (5,3));

assert_eq!(fibonacci_search_with(&vec, &(1,11), &compare), None);
assert_eq!(fibonacci_search_with(&vec, &(1,12), &compare), None);
assert_eq!(fibonacci_search_with(&vec, &(1,13), &compare), None);