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

Commit454682b

Browse files
authored
Merge pull request#16 from dieterpl/master
Added fibonacci search
2 parents18e59a8 +ce87b43 commit454682b

File tree

7 files changed

+92
-7
lines changed

7 files changed

+92
-7
lines changed

‎allalgorithms/searches/__init__.py‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,2 +1,3 @@
11
from .binary_searchimport*
2+
from .fibonacci_searchimport*
23
from .jump_searchimport*
Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
# -*- coding: UTF-8 -*-
2+
#
3+
# Fibonacci search works for a sorted array.
4+
# The All ▲lgorithms library for python
5+
#
6+
# Contributed by: dieterpl
7+
# Github: @dieterpl
8+
#
9+
10+
11+
deffibonacci_search(arr,query):
12+
fib2,fib1=0,1
13+
fib=fib2+fib1
14+
hi=len(arr)-1
15+
whilefib<=hi:
16+
fib2=fib1
17+
fib1=fib
18+
fib=fib2+fib1
19+
offset=-1
20+
whilefib>1:
21+
i=min(offset+fib2,hi)
22+
ifarr[i]<query:
23+
fib=fib1
24+
fib1=fib2
25+
fib2=fib-fib1
26+
offset=i
27+
elifarr[i]>query:
28+
fib=fib2
29+
fib1=fib1-fib2
30+
fib2=fib-fib1
31+
else:
32+
returni
33+
iffib1andarr[offset+1]==query:
34+
returnoffset+1
35+
returnNone

‎changelog.md‎

Lines changed: 8 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -8,11 +8,12 @@ Date: October 9, 2018
88

99
###Algorithms:
1010

11-
-###Sorting
12-
- Bubble Sort
1311
-###Searches
1412
- Merge Sort
1513

14+
-###Sorting
15+
- Bubble Sort
16+
1617
#Version`0.0.1`
1718

1819
Date: TO ADDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD, 2018
@@ -22,10 +23,13 @@ Date: TO ADDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD, 2018
2223
Added:
2324

2425
-###Searches
26+
- Fibonacci Search
27+
- Jump Search
28+
29+
-###Sorting
2530
- Bubble Sort
2631
- Cocktail Shaker Sort
2732
- Insertion Sort
2833
- Pigeonhole Sort
2934
- Selection Sort
30-
- Stooge Sort
31-
- Jump Search
35+
- Stooge Sort

‎docs/readme.md‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -59,6 +59,7 @@ print(binary_search(arr, 3))
5959

6060
-###Searches
6161
-[Binary Search](searches/binary-search)
62+
-[Fibonacci Search](searches/fibonacci-search)
6263
-[Jump Search](searches/jump-search)
6364
-###Sorting
6465
-[Bubble Sort](sorting/bubble-sort)

‎docs/searches/fibonacci-search.md‎

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
#Fibonacci Search
2+
3+
In 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. (Wikipedia)
4+
##Install
5+
6+
```
7+
pip install allalgorithms
8+
```
9+
10+
##Usage
11+
12+
```py
13+
from allalgorithms.searchesimport fibonacci_search
14+
15+
arr= [-2,1,2,7,10,77]
16+
17+
print(fibonacci_search(arr,7))
18+
# -> 3
19+
20+
print(fibonacci_search(arr,3))
21+
# -> None
22+
```
23+
24+
##API
25+
26+
###fibonacci_search(array, query)
27+
28+
>Return array index if its found, otherwise returns`None`
29+
30+
#####Params:
31+
32+
-`array`: Sorted Array
33+
-`query`: Element to search for in the array

‎readme.md‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -59,7 +59,9 @@ print(binary_search(arr, 3))
5959

6060
-###Searches
6161
-[Binary Search](https://python.allalgorithms.com/searches/binary-search)
62+
-[Fibonacci Search](https://python.allalgorithms.com/searches/fibonacci-search)
6263
-[Jump Search](https://python.allalgorithms.com/searches/jump-search)
64+
6365
-###Sorting
6466
-[Bubble Sort](https://python.allalgorithms.com/sorting/bubble-sort)
6567
-[Cocktail Shaker Sort](https://python.allalgorithms.com/sorting/cocktail-shaker-sort)

‎tests/test_searches.py‎

Lines changed: 12 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,10 @@
11
importunittest
22

3-
fromallalgorithms.searchesimport (binary_search,jump_search)
4-
3+
fromallalgorithms.searchesimport (
4+
binary_search,
5+
fibonacci_search,
6+
jump_search
7+
)
58

69
classTestSearches(unittest.TestCase):
710

@@ -12,13 +15,19 @@ def test_binary_search(self):
1215
self.assertEqual(None,binary_search(arr,8))
1316
self.assertEqual(None,binary_search(arr,-1))
1417

18+
deftest_fibonacci_search(self):
19+
arr= [1,2,3,7,10,19,27,77]
20+
self.assertEqual(3,fibonacci_search(arr,7))
21+
self.assertEqual(7,fibonacci_search(arr,77))
22+
self.assertEqual(None,fibonacci_search(arr,8))
23+
self.assertEqual(None,fibonacci_search(arr,-1))
24+
1525
deftest_jump_search(self):
1626
arr= [1,2,3,7,10,19,27,77]
1727
self.assertEqual(3,binary_search(arr,7))
1828
self.assertEqual(7,binary_search(arr,77))
1929
self.assertEqual(None,binary_search(arr,8))
2030
self.assertEqual(None,binary_search(arr,-1))
2131

22-
2332
if__name__=='__main__':
2433
unittest.main()

0 commit comments

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