Fibonacci Search Algorithm C++???

So now I'm creating a program that will search a string using the Fibonacci Search Algorithm. The problem is that the program can't find 9,6,5,3, and 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<iostream>
#include<string>
#include<fstream>
#include<ctime>

using namespace std;

int FibonacciNumber(int arr_last_entry,int &fnm2)
{
	int fn1=1,fn2=-1,temp=0;
	while(fn1<=arr_last_entry)
	{	
		fnm2=fn2;
		temp=fn1;
		fn1=fn1+fn2;
		fn2=temp;	
	}
	return fn2;
}

void FibonacciSearch(string *storewords,string f_skeyword,int left,int right)
{
	int arr_pos=0,fnm1=0,fnm2=0;
	arr_pos=FibonacciNumber(right,fnm2);
	fnm1=arr_pos;

	while((left<right)&&(storewords[left-1+fnm1]!=f_skeyword))
	{
		if(f_skeyword<storewords[left-1+fnm1])
		{
			right=right-fnm2;  //right-=fnm2;
			fnm2=fnm1-fnm2; 
			fnm1=fnm1-fnm2;   //fnm1-=fnm2; 
		}
		else
		{
			left=left+fnm1;
			fnm1=fnm1-fnm2;   //fnm1-=fnm2; 
			fnm2=fnm2-fnm1;   //fnm2-=fnm1;
		}
	}
	if(storewords[left-1+fnm1]==f_skeyword)
		cout<<"YES";
	else
		cout<<"NO";
}

void main(void)
{
	string a[12]={"0","1","2","3","5","6","9","11","15","18","20","23"}; 
	string f="0";   //numbers that can't be found: 9  6  5  3  2
	FibonacciSearch(a,f,0,11);
	system("pause");
}
Last edited on
oh.... and here's the.... err..... psudocode that I tried to code
Please help me

http://www.fileden.com/files/2007/7/2/1231142/fibosearchpsudo.jpg
Last edited on
The array is not lexicographically sorted.
what do you mean by not "lexicographically" sorted? what should I do?? should I change something at the code?
What I mean is, it's sorted by the numeric value the strings represent, not sorted as an array of strings.
It should go
0
1
11
15
18
2
20
23
3
5
6
9

I should note that the order you chose can be used, but only if you redefine what < means for strings. The default operator<() compares strings lexicographically, but you could define an alternate comparison function f() such that f(x,y) is equivalent to to_integer(x)<to_integer(y).
Topic archived. No new replies allowed.