What is the difference between Fibonacci search and binary search?

The main difference between Fibonacci search and binary search lies in the way they divide the search space to locate a target element.

1. Division of Search Space:
- Binary search divides the search space into two equal halves repeatedly until the target element is found or the search space is exhausted.
- Fibonacci search, on the other hand, divides the search space using Fibonacci numbers. It creates a series of Fibonacci numbers that are close to the size of the search space and uses these numbers to divide the space.

2. Midpoint Calculation:
- In binary search, the midpoint of the search space is calculated by taking the average of the low and high indices.
- In Fibonacci search, the midpoint is calculated by using the Fibonacci numbers. The index of the midpoint is determined by subtracting the smaller Fibonacci number from the higher index.

3. Comparison of Target Element:
- Binary search compares the target element with the element at the midpoint of the search space. Based on the comparison, it either continues the search in the left or right half of the search space.
- Fibonacci search compares the target element with the element at the calculated midpoint. If the target element is smaller, it continues the search in the lower Fibonacci subarray. If the target element is larger, it continues the search in the higher Fibonacci subarray.

4. Time Complexity:
- Binary search has a time complexity of O(log n), where n is the size of the search space.
- Fibonacci search has a time complexity of O(log n) as well, but it has a slightly higher constant factor due to the calculation of Fibonacci numbers.

5. Space Complexity:
- Both binary search and Fibonacci search have a space complexity of O(1) as they do not require any additional space apart from the input array.

In summary, while both Fibonacci search and binary search are efficient searching algorithms, they differ in the way they divide the search space and calculate the midpoint. Fibonacci search utilizes Fibonacci numbers for division, while binary search divides the space into two equal halves.