Fibonacci Search Code:
public int fibonacciSearch(int[] nums, int toSearch){
int startIndex=-1; int len=nums.length;
int fibNum1=0; int fibNum2=1;
int fibNum3=fibNum1+fibNum2;
while (fibNum3 < len) {
fibNum1=fibNum2; fibNum2=fibNum3;
fibNum3=fibNum1+fibNum2;
}
while(fibNum3 > 1) {
int checkIndex=startIndex+fibNum1;
if (checkIndex > len-1) {
checkIndex=len-1;
}
if (nums[checkIndex] < toSearch) {
fibNum3=fibNum2; fibNum2=fibNum1;
fibNum1=fibNum3-fibNum2;
startIndex=checkIndex;
} else if ( nums[checkIndex] > toSearch) {
fibNum3=fibNum1; fibNum2=fibNum2-fibNum1;
fibNum1=fibNum3-fibNum2;
} else {
return checkIndex;
}
}
if ((fibNum2 !=0)&&(nums[startIndex+1]==toSearch)) {
return startIndex+1;
}
return -1;
}