Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commite6d916e

Browse files
Fechuliappgurueu
andauthored
feat: add fibonaccisearch algorithm (#244)
* feat: add fibonaccisearch algorithm* test: add test for fibonacci search algorithm* fix: changed variable names and function return* remove redundant@function* fix tests* fix type* fix formatting---------Co-authored-by: Lars Müller <34514239+appgurueu@users.noreply.github.com>Co-authored-by: Lars Mueller <appgurulars@gmx.de>
1 parent869135a commite6d916e

File tree

2 files changed

+75
-0
lines changed

2 files changed

+75
-0
lines changed

‎search/fibonacci_search.ts‎

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
/**
2+
*@description Fibonacci search algorithm for a sorted array.
3+
*
4+
* The algorithm searches for a specific value in a sorted array using Fibonacci numbers
5+
* to divide the array into smaller subarrays. This algorithm is useful for large arrays where
6+
* the cost of accessing elements is high.
7+
*
8+
*@param {number[]} array - sorted list of numbers
9+
*@param {number} target - target number to search for
10+
*@return {number | null} - index of the target number in the list, or null if not found
11+
*@see [FibonacciSearch](https://www.geeksforgeeks.org/fibonacci-search/)
12+
*@example fibonacciSearch([1,2,3], 2) => 1
13+
*@example fibonacciSearch([4,5,6], 2) => null
14+
*/
15+
16+
exportconstfibonacciSearch=(
17+
array:number[],
18+
target:number
19+
):number|null=>{
20+
constarrayLength=array.length
21+
leta=0// (n-2)'th Fibonacci No.
22+
letb=1// (n-1)'th Fibonacci No.
23+
letc=a+b// n'th Fibonacci
24+
25+
while(c<arrayLength){
26+
a=b
27+
b=c
28+
c=a+b
29+
}
30+
31+
letoffset=-1
32+
33+
while(c>1){
34+
leti=Math.min(offset+a,arrayLength-1)
35+
36+
if(array[i]<target){
37+
c=b
38+
b=a
39+
a=c-b
40+
offset=i
41+
}elseif(array[i]>target){
42+
c=a
43+
b=b-a
44+
a=c-b
45+
}else{
46+
// Element found then return index
47+
returni
48+
}
49+
}
50+
51+
if(b&&array[offset+1]===target){
52+
returnoffset+1
53+
}
54+
55+
// Element not found then return null
56+
returnnull
57+
}
Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
import{fibonacciSearch}from'../fibonacci_search'
2+
3+
describe('Fibonacci search',()=>{
4+
test.each([
5+
[[1,2,3],2,1],
6+
[[4,5,6],2,null],
7+
[[10,22,35,40,45,50,80,82,85,90,100],85,8],
8+
[[],1,null],
9+
[[1],1,0],
10+
[[1,3,5,7,9,11,13],11,5],
11+
[[1,3,5,7,9,11,13],8,null]
12+
])(
13+
'of %o, searching for %o, expected %i',
14+
(array:number[],target:number,expected:number|null)=>{
15+
expect(fibonacciSearch(array,target)).toBe(expected)
16+
}
17+
)
18+
})

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp