Problem with Fibonacci's sequence and Binary search

[windmilltaker]

So, I have a problem with the source code down there. As you can see, the program is used to search the Fibonacci sequence with the Binary search method.
The problem here is, if I input a number equal or higher than 144(witch is in the Fibonacci sequence), the program just writes that there isn't a number like that in the sequence.

#include <iostream>
using namespace std;

int searchFibNiza (int*niz, int d, int trBroj)
{
	int indp=0;
	int indz=d-1;
	int indpivot;
	while (indp<=indz)
	{
		indpivot=(indp+indz)/2;
		if(niz[indpivot]==trBroj)
		{
			return indpivot; 
		}
		else if (niz[indpivot]<trBroj)
		{
			indp=indpivot+1;
		}
		else if (niz[indpivot]>trBroj)
		{
			indz=indpivot-1;
 		}
 	}
	 return 0;
}

int main ()
{
	int trBroj;
	cin>>trBroj;
	int d=trBroj+5;
	int*niz = new int[d];
	for (int i=0; i<d; i++)
	{
 		if (i==0)
		 {
			niz[i]=0;
		 } 
		else if (i==1)
		 { 
			niz[i] = 1;
		 }
		else 
		 {
			niz[i] = niz[i -1] + niz[i -2];
		 }
	}
        int v=searchFibNiza(niz, d, trBroj);
        if (trBroj==0)
        {
	                cout<<"Zero is on the 1. place.<<endl;
        }
        else if (trBroj==1)
        {
	                cout<<"Number 1 is on the 2. i 3. place."<<endl;
         }   
         else if (v==0)
         {
	                cout<<"The number is not here"<<endl;
         }
         else 
         {
	                cout<<"The number "<<trBroj<<" is on the "<<v<<". place"<<endl;
         }
	delete[] niz;
	return 0;
} 

[shadder]

I think int is not big enough for your code try unsigned long int

[fg109]

You can also reduce the size of your array so you don't have to calculate all those numbers. 144 is the 12th (13th if you count 0) Fibonacci number, but you're trying to find the first 144 Fibonacci numbers.

We know that the nth Fibonacci number (F_n) is less than twice as large as the one before it (F_n-1) so I think log2 can help to figure out a smaller array size.

From looking at the first 100 Fibonacci numbers, I think you can change line 33 to int d = floor(log2(trBroj)) * 2 + 5; and still have it work.

[windmilltaker]

Thank you both for your quick answers!
programmer007 - Yeah, true, but the purpose of the program isn't to be too complex, so it really isn't necessary to go to the really high numbers that unsigned long futures.

fg109 - That change worked. Thank you! Now it goes over 20+ places.

[fg109]

@windmilltaker

Well, I did some more thinking and realized that what I told you isn't a great idea. Since the next Fibonacci number is less than twice as large as the previous, then that means that the numbers occur more frequently than powers of two. More frequent means the array would need to be larger.

I tested the calculation I gave you for the first 100 Fibonacci numbers, but eventually it won't be large enough to contain all of them. As for when that happens, I don't know.

As for what programmer007 was saying, it's because you were trying to calculate so many Fibonacci numbers. The Fibonacci numbers go over 2 billion by around the 50th term in the sequence, and int can only store from around -2 billion to +2 billion.