fibonacci_search.cpp File Reference

Fibonacci search algorithm More...

#include <iostream>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <algorithm>

Include dependency graph for fibonacci_search.cpp:

Go to the source code of this file.

Functions
int	fibonacci_search (const std::vector< int > &arr, int value)
	using fibonacci search algorithm finds an index of a given element in a sorted array
bool	no_occurence_tests ()
	random tests for checking performance when an array doesn't contain an element
bool	random_tests ()
	random tests which cover cases when we have one, multiple or zero occurences of the value we're looking for
int	main ()

Detailed Description

Fibonacci search algorithm

Author

sprintyaf

Definition in file fibonacci_search.cpp.

Function Documentation

fibonacci_search()

int fibonacci_search	(	const std::vector< int > &	arr,
		int	value )

using fibonacci search algorithm finds an index of a given element in a sorted array

Parameters

arr	sorted array
value	value that we're looking for

Returns

if the array contains the value, returns an index of the element. otherwise -1.

Definition at line 23 of file fibonacci_search.cpp.

                                                          {
    // initialize last and current members of Fibonacci sequence 
    int last = 0, current = 1;
    int length = arr.size(); // array size
    // next member of Fibonacci sequence which is "last" + "current"
    int next = last + current; 
 
    // "next" will store the smallest Fibonacci number greater or equal to "length"
    while(next < length){
        last = current;
        current = next;
        next = last + current;
    }
 
    // "offset" is the end of eliminated range from front
    int offset = -1, index;
    // while loop until there are elements left to consider.
    // when "next" becomes 1, last is equal to 0, so search is done,
    // because arr[offset] will already be eliminated
    while(next > 1){
        // check if "last" is valid location
        index = std::min(offset + last, length-1);
        // if value is greater than the value at "index", eliminate the subarray from offset to index
        if(arr[index] < value){
            next = current;
            current = last;
            last = next - current;
            offset = index;
        // if value is less than the value at "index", eliminate the subarray after index+1
        } else if(arr[index] > value){
            next = last;
            current = current - last;
            last = next - current;
        // element is found
        } else {
            return index;
        }
    }
    // comparing the last element
    if(current && !arr.empty() && arr[offset+1] == value){
        return offset+1;
    }
    // value was not found, return -1
    return -1;
}

main()

int main

(

void

)

Main Function testing the algorithm

Definition at line 123 of file fibonacci_search.cpp.

           {
    assert(no_occurence_tests());
    assert(random_tests());
    return 0;
}

no_occurence_tests()

bool no_occurence_tests

(

)

random tests for checking performance when an array doesn't contain an element

Definition at line 72 of file fibonacci_search.cpp.

                         {
    bool passed = true;
    int rand_num, rand_value, index, num_tests = 1000;
    std::vector<int> arr;
    while(num_tests--){
        arr.clear();
        for(int i = 0; i < 100; i++){
            rand_num = std::rand() % 1000;
            arr.push_back(rand_num);
        }
        rand_value = std::rand() % 1000;
        while(std::find(arr.begin(), arr.end(), rand_value) != arr.end()){
            std::remove(arr.begin(), arr.end(), rand_value);
        }
        sort(arr.begin(), arr.end());
        index = fibonacci_search(arr, rand_value);
        passed = passed && (index == -1);
    }
    return passed;
}

random_tests()

bool random_tests

(

)

random tests which cover cases when we have one, multiple or zero occurences of the value we're looking for

Definition at line 96 of file fibonacci_search.cpp.

                   {
    bool passed = true;
    int rand_num, rand_value, index, real_value, num_tests = 10000;
    std::vector<int> arr;
    while(num_tests--){
        arr.clear();
        for(int i = 0; i < 100; i++){
            rand_num = std::rand() % 1000;
            arr.push_back(rand_num);
        }
        rand_value = std::rand() % 1000;
        std::sort(arr.begin(), arr.end());
        index = fibonacci_search(arr, rand_value);
        if(index != -1){
            real_value = arr[index];
            passed = passed && (real_value == rand_value);
        } else {
            passed = passed && (std::find(arr.begin(), arr.end(), rand_value) == arr.end());
        }
    }
    return passed;
}