What is Fibonacci search?

Web Development
,
#1

Fibonacci search is a search algorithm that applies to a sorted array. It makes use of a divide-and-conquer approach that can significantly reduce the time needed in order to reach the target element.

The fibonacci search is an efficient searching algorithm which works on sorted array of length n. it is a comparison-based algorithm and it returns the index of an element which we want to search in array and if that element is not there then it returns -1.
n computer science, the Fibonacci search technique is a method of searching a sorted array using a divide and conquer algorithm that narrows down possible locations with the aid of Fibonacci numbers.

#2

he fibonacci search is an efficient searching algorithm which works on sorted array of length n. it is a comparison-based algorithm and it returns the index of an element which we want to search in array and if that element is not there then it returns -1.

Examples:

1. Input: arr[] = {20, 30, 40, 50, 60}, x = 50

Output: 3

Fibonacci search is an efficient search and comparison-based algorithm. In this, the fibonacci numbers are used to search an element in given sorted array.

Similarities with Binary Search:

  • Fibonacci search works on sorted array only as the binary search.
  • The time taken by fibonacci search in worst case is O( log n) which is similar to the binary search.
  • The divide and conquer technique is used by fibonacci search.