## Explain what is Fibonacci Search technique?

Fibonacci Search is a search algorithm that finds the position of a target value in a sorted array using the Fibonacci sequence. It is an efficient searching technique that has a time complexity of O(log n).

Here’s how the Fibonacci Search algorithm works:

- Determine the Fibonacci numbers:
- Start by generating a sequence of Fibonacci numbers that includes numbers greater than or equal to the size of the array to be searched.
- The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones: 0, 1, 1, 2, 3, 5, 8, 13, 21, …

- Initialize variables:
- Let
`n`

be the size of the array. - Initialize two pointers:
`left`

pointing to the start of the array (index 0) and`right`

pointing to the end of the array (index n-1). - Initialize an index variable
`mid`

as the minimum of`left + Fibonacci[k-2]`

and`n-1`

(where`k`

is the smallest Fibonacci number greater than or equal to`n`

).

- Let
- Search Process:
- Compare the target value with the element at index
`mid`

. - If the target value is equal to the element at
`mid`

, the search is successful, and`mid`

is the position of the target value. - If the target value is less than the element at
`mid`

, update`right`

to`mid - 1`

and recalculate`mid`

using the Fibonacci sequence (moving left in the array). - If the target value is greater than the element at
`mid`

, update`left`

to`mid + 1`

and recalculate`mid`

using the Fibonacci sequence (moving right in the array). - Repeat the comparison until the target value is found or
`left`

becomes greater than`right`

.

- Compare the target value with the element at index
- Termination:
- The search terminates when the target value is found or
`left`

becomes greater than`right`

, indicating that the target value is not present in the array.

- The search terminates when the target value is found or

Fibonacci Search works by dividing the search space into smaller subarrays using Fibonacci numbers. It narrows down the search range by moving left or right based on the comparison with the target value. The use of Fibonacci numbers ensures efficient movement and a balanced search space.

Fibonacci Search is particularly useful when the array size is large and unevenly distributed. It performs well in scenarios where random access to elements is costly (e.g., when accessing elements from external storage).

However, it’s worth noting that Fibonacci Search is not commonly used in practice compared to other search algorithms such as binary search. This is because binary search has a similar time complexity of O(log n) but performs fewer comparisons and has better cache locality.