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

Commitbe2110e

Browse files
authored
Merge branch 'master' into palindrome_checker
2 parents6669e31 +454682b commitbe2110e

File tree

9 files changed

+162
-15
lines changed

9 files changed

+162
-15
lines changed

‎allalgorithms/searches/__init__.py‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1 +1,3 @@
11
from .binary_searchimport*
2+
from .fibonacci_searchimport*
3+
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
Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
# -*- coding: UTF-8 -*-
2+
#
3+
# Jump search works for a sorted array.
4+
# The All ▲lgorithms library for python
5+
#
6+
# Contributed by: pieromoto
7+
# Github: @pieromoto
8+
#
9+
importmath
10+
11+
defjump_search(arr,query):
12+
arr_len=len(arr)
13+
prev=0
14+
step=int(math.sqrt(arr_len))
15+
16+
foriinrange(step-1,arr_len,step):
17+
if(arr[i]>=query):
18+
break
19+
prev=i
20+
21+
forjinrange(prev,arr_len):
22+
if(arr[j]==query):
23+
returnj
24+
25+
returnNone

‎changelog.md‎

Lines changed: 8 additions & 13 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,22 +23,16 @@ 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
3035
- Stooge Sort
3136

32-
#Version`0.0.2`
33-
34-
Date: October 10, 2018
35-
36-
###Algorithms:
37-
38-
Added:
39-
4037
-###String
41-
- Palindrome Checker
42-
43-
38+
- Palindrome Checker

‎docs/readme.md‎

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

6060
-###Searches
6161
-[Binary Search](searches/binary-search)
62+
-[Fibonacci Search](searches/fibonacci-search)
63+
-[Jump Search](searches/jump-search)
6264
-###Sorting
6365
-[Bubble Sort](sorting/bubble-sort)
6466
-[Cocktail Shaker Sort](sorting/cocktail-shaker-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

‎docs/searches/jump-search.md‎

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
#Jump Search
2+
3+
In computer science, jump search is a search algorithm for sorted array which find the element by jumping ahead by fixed steps or skipping some elements in place of searching all elements.
4+
5+
##Install
6+
7+
```
8+
pip install allalgorithms
9+
```
10+
11+
##Usage
12+
13+
```py
14+
from allalgorithms.searchesimport jump_search
15+
16+
arr= [-2,1,2,7,10,77]
17+
18+
print(jump_search(arr,7))
19+
# -> 3
20+
21+
print(jump_search(arr,3))
22+
# -> None
23+
```
24+
25+
##API
26+
27+
###jump_search(array, query)
28+
29+
>Return array index if its found, otherwise returns`None`
30+
31+
#####Params:
32+
33+
-`arr`: Sorted Array
34+
-`query`: Element to search for in the array
35+
36+

‎readme.md‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -59,6 +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)
63+
-[Jump Search](https://python.allalgorithms.com/searches/jump-search)
64+
6265
-###Sorting
6366
-[Bubble Sort](https://python.allalgorithms.com/sorting/bubble-sort)
6467
-[Cocktail Shaker Sort](https://python.allalgorithms.com/sorting/cocktail-shaker-sort)

‎tests/test_searches.py‎

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

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

69
classTestSearches(unittest.TestCase):
710

@@ -12,6 +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+
25+
deftest_jump_search(self):
26+
arr= [1,2,3,7,10,19,27,77]
27+
self.assertEqual(3,binary_search(arr,7))
28+
self.assertEqual(7,binary_search(arr,77))
29+
self.assertEqual(None,binary_search(arr,8))
30+
self.assertEqual(None,binary_search(arr,-1))
1531

1632
if__name__=='__main__':
1733
unittest.main()

0 commit comments

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