CC-9 : Implement Fibonacci Search Algorithm.

Description:

TThe Fibonacci search algorithm works on sorted lists. The algorithm partitions the list by using partitions with size equal to consecutive Fibonacci numbers (that is, the partition sizes are 1,1,2,3,5,8…). Given an input array and an element to be searched, search the required element in the input array using Fibonacci search.

Test cases and expected outputs:

Input Parameters	Expected outputs
Array: 3, 22, 44, 67, 77, 96, 122, 144, 201,	122 found at index 6 76 found at index -1 3 found at index 0 201 found at index 8

Pseudocode:

Fibonacci Search(nums[], toSearch):

Integer array named nums, and integer named toSearch to be searched are received as input parameters.

Set integer variable idx to -1.

Set integer variable len to nums.length.

Set integer variable fibNum1 to 0.

Set integer variable fibNum2 to 1.

Set integer variable fibNum3 to fibNum1+fibNum2.

In the next step we will find the largest Fibonacci triplet sized partitions that can be formed in the nums array.

While (fibNum3 < nums.length) and nums[firstIdx] <= toSearch do the following steps:

Set fibNum1=fibNum2.

Set fibNum2=fibNum3.

Set fibNum3 to fibNum1+fibNum2.

Now, we need to reduce our Fibonacci partitions as shown in next step till we find the number toSearch, or until we have searched whole array but have not found toSearch.

While (fibNum3 >1):

Set currIdx to idx+fibNum1.

If currIDx >len-1:

Set currIdx=len-1.

If (nums[currIdx]

Set fibNum3=fibNum2.

Set fibNum2=fibNum1.

Set fibNum1=fibNum3-fibNum2.

Set Idx=currIdx.

Else if (nums[currIdx]>toSearch:

Set fibNum3=fibNum1.

Set fibNum2=fibNum2-fibNum1.

Set fibNum1=fibNum3-fubNum2.

Else:

We have found the index of toSearch. Return currIdx.

If fibNum2 !=0 and nums[idx+1]==toSearch then return idx+1.

If toSearch is not found in code above return -1, as the required element does not exist within the input array.

Code:

public int fibonacciSearch(int[] nums, int toSearch){
	int idx=-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 currIdx=idx+fibNum1;
		if (currIdx > len-1) {
			currIdx=len-1;
		}
		if (nums[currIdx] < toSearch) {
			fibNum3=fibNum2;
			fibNum2=fibNum1;
			fibNum1=fibNum3-fibNum2;
			idx=currIdx;
		} else if (nums[currIdx]>toSearch) {
			fibNum3=fibNum1;
			fibNum2=fibNum2-fibNum1;
			fibNum1=fibNum3-fibNum2;
		} else {
			return currIdx;
		}		
	}
	if ((fibNum2 !=0)&&(nums[idx+1]==toSearch)) {
		return idx+1;
	}
	return -1;
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

public int fibonacciSearch(int[] nums, int toSearch){
	int idx=-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 currIdx=idx+fibNum1;
		if (currIdx > len-1) {
			currIdx=len-1;
		}
		if (nums[currIdx] < toSearch) {
			fibNum3=fibNum2;
			fibNum2=fibNum1;
			fibNum1=fibNum3-fibNum2;
			idx=currIdx;
		} else if (nums[currIdx]>toSearch) {
			fibNum3=fibNum1;
			fibNum2=fibNum2-fibNum1;
			fibNum1=fibNum3-fibNum2;
		} else {
			return currIdx;
		}		
	}
	if ((fibNum2 !=0)&&(nums[idx+1]==toSearch)) {
		return idx+1;
	}
	return -1;
}


public static void main(String[] args) {
	/***********************
	 Test cases given below:
	 **********************/
	int retVal;
	try {
	
	SearchFibonacciSearch search=new SearchFibonacciSearch();
	int[] nums= { 3,22,44,67,77,96,122, 144, 201};
	int toSearch=122;
	retVal=search.fibonacciSearch(nums, toSearch);
	
	System.out.println("\nArray:");
	int arrayIndex=0;
	for (arrayIndex=0; arrayIndex < nums.length; arrayIndex++) {
		System.out.print(nums[arrayIndex]+", ");		
	} 
	
	System.out.println("\n\n"+toSearch + " found at index "+ retVal);	
	
	toSearch=76;
	retVal=search.fibonacciSearch(nums, toSearch);
	System.out.println("\n"+toSearch + " found at index "+ retVal);	
	
	toSearch=3;
	retVal=search.fibonacciSearch(nums, toSearch);
	System.out.println("\n"+toSearch + " found at index "+ retVal);	
	
	toSearch=201;
	retVal=search.fibonacciSearch(nums, toSearch);
	System.out.println("\n"+toSearch + " found at index "+ retVal);	
	
	toSearch=22;
	retVal=search.fibonacciSearch(nums, toSearch);
	System.out.println("\n"+toSearch + " found at index "+ retVal);	
	
	toSearch=144;
	retVal=search.fibonacciSearch(nums, toSearch);
	System.out.println("\n"+toSearch + " found at index "+ retVal);	
	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}

}