Fibonacci search algorithm
More...
#include <iostream>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <algorithm>
|
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 () |
|
◆ 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.
23 {
24
25 int last = 0, current = 1;
26 int length = arr.
size();
27
28 int next = last + current;
29
30
31 while(next < length){
32 last = current;
34 next = last + current;
35 }
36
37
38 int offset = -1, index;
39
40
41
42 while(next > 1){
43
44 index =
std::min(offset + last, length-1);
45
46 if(arr[index] < value){
48 current = last;
49 last =
next - current;
50 offset = index;
51
52 } else if(arr[index] > value){
54 current = current - last;
55 last =
next - current;
56
57 } else {
58 return index;
59 }
60 }
61
62 if(current && !arr.
empty() && arr[offset+1] == value){
63 return offset+1;
64 }
65
66 return -1;
67}
◆ main()
Main Function testing the algorithm
123 {
126 return 0;
127}
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
bool no_occurence_tests()
random tests for checking performance when an array doesn't contain an element
Definition fibonacci_search.cpp:72
◆ no_occurence_tests()
bool no_occurence_tests |
( |
| ) |
|
random tests for checking performance when an array doesn't contain an element
72 {
73 bool passed = true;
74 int rand_num, rand_value, index, num_tests = 1000;
76 while(num_tests--){
78 for(int i = 0; i < 100; i++){
81 }
85 }
88 passed = passed && (index == -1);
89 }
90 return passed;
91}
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
Definition fibonacci_search.cpp:23
◆ random_tests()
random tests which cover cases when we have one, multiple or zero occurences of the value we're looking for
96 {
97 bool passed = true;
98 int rand_num, rand_value, index, real_value, num_tests = 10000;
100 while(num_tests--){
102 for(int i = 0; i < 100; i++){
105 }
109 if(index != -1){
110 real_value = arr[index];
111 passed = passed && (real_value == rand_value);
112 } else {
114 }
115 }
116 return passed;
117}