FilesExpand file tree

 master

/

FibonacciSearch.js

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

77 lines (70 loc) · 2.48 KB

 master

/

FibonacciSearch.js

Copy path

Top

File metadata and controls

• Code
• Blame

77 lines (70 loc) · 2.48 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

/****************************************************************************

* Fibonacci Search JavaScript Implementation

* Author Alhassan Atama Isiaka

* Version v1.0.0

* Copyright 2020

* https://github.com/komputarist

*

* This implementation is based on Generalizing the Fibonacci search we

* define the Fibonacci search of degree K. Like the Fibonacci search,

* which it reduces to for K = 2, the Fibonacci search of degree K

* involves only addition and subtraction.

* Capocelli R.M. (1991) A Generalization of the Fibonacci Search. In:

* Bergum G.E., Philippou A.N., Horadam A.F. (eds) Applications of Fibonacci

* Numbers. Springer, Dordrecht. https://doi.org/10.1007/978-94-011-3586-3_9

*

* This snippet is free. Feel free to improve on it

*

* We define a function fibonacciSearch() that takes an array of numbers,

* the item (number) to be searched for and the length of the items in the array

****************************************************************************/

export const fibonacciSearch = (arr, x, n) => {

let fib2 = 0 // (K-2)'th Fibonacci Number

let fib1 = 1 // (K-1)'th Fibonacci Number.

let fibK = fib2 + fib1 // Kth Fibonacci

/* We want to store the smallest fibonacci number smaller such that

number is greater than or equal to n, we use fibK for this */

while (fibK < n) {

fib2 = fib1

fib1 = fibK

fibK = fib2 + fib1

}

// This marks the eliminated range from front

let offset = -1

/* while there are elements to be checked. We compare arr[fib2] with x.

When fibM becomes 1, fib2 becomes 0 */

while (fibK > 1) {

// Check if fibK is a valid location

const i = Math.min(offset + fib2, n - 1)

/* If x is greater than the value at

index fib2, Partition the subarray array

from offset to i */

if (arr[i] < x) {

fibK = fib1

fib1 = fib2

fib2 = fibK - fib1

offset = i

/* If x is greater than the value at

index fib2, cut the subarray array

from offset to i */

} else if (arr[i] > x) {

fibK = fib2

fib1 = fib1 - fib2

fib2 = fibK - fib1

} else {

// return index for found element

return i

}

}

// comparing the last element with x */

if (fib1 && arr[offset + 1] === x) {

return offset + 1

}

// element not found. return -1

return -1

}

// Example

// const myArray = [10, 22, 35, 40, 45, 50, 80, 82, 85, 90, 100]

// const n = myArray.length

// const x = 90

// const fibFinder = fibonacciSearch(myArray, x, n)