Fibonacci Search – Data Structure Questions and Answers

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

1. 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

Explanation: When access speed is determined by the previous location visited, Fibonacci search outperforms binary search because it works best on locations with lower dispersion. Unsorted arrays will not operate with Factorial scan. The input should be a sorted list, or the array should be sorted before applying the Fibonacci algorithm.

2. What is the length of the step in jump search?
A) n
B) n/2
C) sqrt(n)
D) 1
Explanation: If the step size is 1, the search becomes linear; if it is n, we reach the end of the list in just one step; if it is n/2, it resembles binary search; hence, sqrt is found to be the most efficient step size (n).

3. 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;
}```

Explanation: A sequential search is performed in this block after finding the right block of k elements.

4. What is the time complexity of Jump Search?
A) O(logn)
B) O(n)
C) O(sqrt(n))
D) O(nlogn)

Explanation: The complexity is obviously O(sqrt(n)) since the phase size is sqrt(n).

5. Which algorithmic technique does Fibonacci search use?
A) Brute force
B) Divide and Conquer
C) Greedy Technique
D) Backtracking

Explanation: We divide the given array into two subarrays for each iteration (not necessarily equal).

6. 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)

Explanation: None.

7. Write a function for the Fibonacci search method.
A)

```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;
}```

```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)

```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)

```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;
}
}```

Explanation: We use Fibonacci numbers instead of the centre of the array as the point of array division, and the division index is exclusively between two Fibonacci numbers.

8. What is the time complexity of Fibonacci Search?
A) O(logn)

B) O(n)
C) O(n2)
D) O(nlogn)

Explanation: In the case of large arrays, it is better than binary search since it splits the array into two bits, but they are not identical. Its time complexity is O(logn).

The Fibonacci search technique is a method for searching a sorted array using a divide and conquer algorithm that uses Fibonacci numbers to narrow down possible locations. Fibonacci search divides the sorted array into two sections of sizes that are consecutive Fibonacci numbers, as opposed to binary search, which divides the array into two equal-sized parts, one of which is analysed further. If the data is stored on magnetic tape and the seek time is determined by the current head location, a tradeoff between a longer seek time and more comparisons which result in a distorted search algorithm similar to Fibonacci search.