Data Structure Questions and Answers – Fibonacci Search

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Fibonacci Search”.

1. Which algorithmic technique does Fibonacci search use?
a) Brute force
b) Divide and Conquer
c) Greedy Technique
d) Backtracking
View Answer

Answer: b
Explanation: With every iteration, we divide the given array into two sub arrays(not necessarily equal).

2. Choose the recursive formula for the Fibonacci series.(n>=1)
a) F(n) = F(n+1) + F(n+2)
b) F(n) = F(n) + F(n+1)
c) F(n) = F(n-1) + F(n-2)
d) F(n) = F(n-1) – F(n-2)
View Answer

Answer: c
Explanation: None.

3. Write a function for the Fibonacci search method.
a)

advertisement
advertisement
public static int fibSearch(final int key, final int[] a) 
{
        int low = 0;
        int high = a.length - 1;
        int fibCurrent = 1;
        int fibPrev = 1;
        int N = a.length;
        while (low <= high) 
        {
            while(fibCurrent < N)
            {
                int tmp = fibCurrent + fibPrev;
                fibPrev = fibCurrent;
                fibCurrent = tmp;
                N = N - (fibCurrent - fibPrev);
            }
            final int mid = low + (high - low) - (fibCurrent + fibPrev);
            if      (key < a[mid]) high = mid - 1;
            else if (key > a[mid]) low = mid + 1;
            else return mid;
        }
        return -1;
}

b)

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
public static int fibSearch(final int key, final int[] a) 
{
        int low = 0;
        int high = a.length - 1;
        int fibCurrent = 1;
        int fibPrev = 1;
        int N = a.length;
        while (low <= high) 
        {
            int tmp = fibCurrent + fibPrev;
            fibPrev = fibCurrent;
            fibCurrent = tmp;
            N = N - (fibCurrent - fibPrev);
            final int mid = low + (high - low) - (fibCurrent + fibPrev);
            if      (key < a[mid]) high = mid - 1;
            else if (key > a[mid]) low = mid + 1;
            else return mid;
        }
        return -1;
}

c)

advertisement
public static int fibSearch(final int key, final int[] a) 
{
        int low = 0;
        int high = a.length - 1;
        int fibCurrent = 1;
        int fibPrev = 1;
        int N = a.length;
        while (low <= high) 
        {
            while(fibCurrent < N)
            {
                int tmp = fibCurrent + fibPrev;
                fibPrev = fibCurrent;
                fibCurrent = tmp;
                N = N - (fibCurrent - fibPrev);
            }
            final int mid = low + (high - low) - (fibCurrent + fibPrev);
            if      (key < a[mid]) low = mid + 1;
            else if (key > a[mid]) high = mid - 1;
            else return mid;
        }
}

d)

advertisement
public static int fibSearch(final int key, final int[] a) 
{
        int low = 0;
        int high = a.length - 1;
        int fibCurrent = 1;
        int fibPrev = 1;
        int N = a.length;
        while (low <= high) 
        {
            while(fibCurrent < N)
            {
                int tmp = fibCurrent + fibPrev;
                fibPrev = fibCurrent;
                fibCurrent = tmp;
                N = N - (fibCurrent - fibPrev);
            }
            final int mid = low + (high - low) - (fibCurrent + fibPrev);
            if      (key < a[mid]) low = mid - 1;
            else if (key > a[mid]) high = mid - 1;
            else return mid;
        }
}
View Answer
Answer: a
Explanation: Here instead of choosing middle of the array as a point of array division, we use Fibonacci numbers, the division index are strictly between two Fibonacci numbers.
 
 

4. What is the time complexity of Fibonacci Search?
a) O(logn)
b) O(n)
c) O(n2)
d) O(nlogn)
View Answer

Answer: a
Explanation: Since it divides the array into two parts, although not equal, its time complexity is O(logn), it is better than binary search in case of large arrays.

5. Which of the following is not an advantage of Fibonacci Search?
a) When the element being searched for has a non uniform access storage
b) Can be used in magnetic tapes
c) Can be used for large arrays which do not fit in the CPU cache or in the RAM
d) It can be applied efficiently on unsorted arrays
View Answer

Answer: d
Explanation: When the speed of access depends on the location previously accessed, Fibonacci search is better compared to binary search as it performs well on those locations which have lower dispersion. Fibonacci search won’t work on unsorted arrays. The input should be a sorted array or array should be sorted before Fibonacci search.

6. What is the length of the step in jump search?
a) n
b) n/2
c) sqrt(n)
d) 1
View Answer

Answer: c
Explanation: If the step size is 1, it becomes a linear search, if it is n, we reach the end of the list in just on step, if it is n/2, it becomes similar to binary search, therefore the most efficient step size is found to be sqrt(n).

7. Select the code snippet for Jump Search.
a)

public int jumpSearch(int arr[], int key)
{
	int size = arr.length;
	int step = floor(sqrt(size));
	int prev = 0;
	while (arr[(step > size ? step : size)] < key) 
        {
		prev = step;
		step += floor(sqrt(size));
		if (step >= size) 
                {
			return -1;
		}
	}
	while (arr[prev] < key) 
        {
		prev++;
		if (prev == (step < size ? step : size)) 
                {
			return -1;
		}
	}
	if (arr[prev] == key) 
        {
		return prev;
	}
	return -1;
}

b)

public int jumpSearch(int arr[], int key)
{
	int size = arr.length;
	int step = floor(sqrt(size));
	int prev = 0;
	while (arr[(step < size ? step : size)] < key) 
        {
		prev = step;
		step += floor(sqrt(size));
		if (step >= size) 
                {
			return -1;
		}
	}
	while (arr[prev] < key) 
        {
		prev++;
		if (prev == (step < size ? step : size)) 
                {
			return -1;
		}
	}
	if (arr[prev] == key) 
        {
		return prev;
	}
	return -1;
}

c)

public int jumpSearch(int arr[], int key)
{
	int size = arr.length;
	int step = floor(sqrt(size));
	int prev = 0;
	while (arr[(step > size ? step : size)] < key) 
        {
		prev = step;
		step += floor(sqrt(size));
		if (step >= size) 
                {
			return -1;
		}
	}
	while (arr[prev] > key) 
        {
		prev++;
		if (prev == (step < size ? step : size)) 
                {
			return -1;
		}
	}
	if (arr[prev] == key) 
        {
		return prev;
	}
	return -1;
}

d)

public int jumpSearch(int arr[], int key)
{
	int size = arr.length;
	int step = floor(sqrt(size));
	int prev = 0;
	while (arr[(step > size ? step : size)] < key) 
        {
		prev = step;
		step += floor(sqrt(size));
		if (step <= size) 
                {
			return -1;
		}
	}
	while (arr[prev] > key) 
        {
		prev++;
		if (prev == (step < size ? step : size)) 
                {
			return -1;
		}
	}
	if (arr[prev] == key) 
        {
		return prev;
	}
	return -1;
}
View Answer
Answer: b
Explanation: After finding the correct block of k elements, a sequential search is performed in this block.
 
 

8. What is the time complexity of Jump Search?
a) O(logn)
b) O(n)
c) O(sqrt(n))
d) O(nlogn)
View Answer

Answer: c
Explanation: Since the size of the step is sqrt(n), the complexity is also obviously O(sqrt(n)).

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.

To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.