Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
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:

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 More...
 
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

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
arrsorted array
valuevalue that we're looking for
Returns
if the array contains the value, returns an index of the element. otherwise -1.
23  {
24  // initialize last and current members of Fibonacci sequence
25  int last = 0, current = 1;
26  int length = arr.size(); // array size
27  // next member of Fibonacci sequence which is "last" + "current"
28  int next = last + current;
29 
30  // "next" will store the smallest Fibonacci number greater or equal to "length"
31  while(next < length){
32  last = current;
33  current = next;
34  next = last + current;
35  }
36 
37  // "offset" is the end of eliminated range from front
38  int offset = -1, index;
39  // while loop until there are elements left to consider.
40  // when "next" becomes 1, last is equal to 0, so search is done,
41  // because arr[offset] will already be eliminated
42  while(next > 1){
43  // check if "last" is valid location
44  index = std::min(offset + last, length-1);
45  // if value is greater than the value at "index", eliminate the subarray from offset to index
46  if(arr[index] < value){
47  next = current;
48  current = last;
49  last = next - current;
50  offset = index;
51  // if value is less than the value at "index", eliminate the subarray after index+1
52  } else if(arr[index] > value){
53  next = last;
54  current = current - last;
55  last = next - current;
56  // element is found
57  } else {
58  return index;
59  }
60  }
61  // comparing the last element
62  if(current && !arr.empty() && arr[offset+1] == value){
63  return offset+1;
64  }
65  // value was not found, return -1
66  return -1;
67 }
Here is the call graph for this function:

◆ main()

int main ( void  )

Main Function testing the algorithm

123  {
124  assert(no_occurence_tests());
125  assert(random_tests());
126  return 0;
127 }
Here is the call graph for this function:
random_tests
bool random_tests()
random tests which cover cases when we have one, multiple or zero occurences of the value we're looki...
Definition: fibonacci_search.cpp:96
std::vector::size
T size(T... args)
std::min
T min(T... args)
no_occurence_tests
bool no_occurence_tests()
random tests for checking performance when an array doesn't contain an element
Definition: fibonacci_search.cpp:72
std::vector::empty
T empty(T... args)
std::next
T next(T... args)