JavaScript/Search/FibonacciSearch.js at master · MMABSOUT/JavaScript · GitHub

History

77 lines (70 loc) · 2.48 KB

Raw

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

* Fibonacci Search JavaScript Implementation

* Author Alhassan Atama Isiaka

* Version v1.0.0

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

JavaScript/Search/FibonacciSearch.js at master · MMABSOUT/JavaScript · GitHub

Expand file tree

Breadcrumbs

FibonacciSearch.js

Latest commit

History

Breadcrumbs

FibonacciSearch.js

File metadata and controls