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

Commit18e59a8

Browse files
authored
Merge pull requestabranhe#17 from pieromoto/jump_search
Added jump search
2 parentsee71bfe +2ae94f9 commit18e59a8

File tree

7 files changed

+73
-1
lines changed

7 files changed

+73
-1
lines changed

‎allalgorithms/searches/__init__.py‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1 +1,2 @@
11
from .binary_searchimport*
2+
from .jump_searchimport*
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: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -28,3 +28,4 @@ Added:
2828
- Pigeonhole Sort
2929
- Selection Sort
3030
- Stooge Sort
31+
- Jump Search

‎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+
-[Jump Search](searches/jump-search)
6263
-###Sorting
6364
-[Bubble Sort](sorting/bubble-sort)
6465
-[Cocktail Shaker Sort](sorting/cocktail-shaker-sort)

‎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: 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](https://python.allalgorithms.com/searches/binary-search)
62+
-[Jump Search](https://python.allalgorithms.com/searches/jump-search)
6263
-###Sorting
6364
-[Bubble Sort](https://python.allalgorithms.com/sorting/bubble-sort)
6465
-[Cocktail Shaker Sort](https://python.allalgorithms.com/sorting/cocktail-shaker-sort)

‎tests/test_searches.py‎

Lines changed: 8 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
importunittest
22

3-
fromallalgorithms.searchesimportbinary_search
3+
fromallalgorithms.searchesimport(binary_search,jump_search)
44

55

66
classTestSearches(unittest.TestCase):
@@ -12,6 +12,13 @@ def test_binary_search(self):
1212
self.assertEqual(None,binary_search(arr,8))
1313
self.assertEqual(None,binary_search(arr,-1))
1414

15+
deftest_jump_search(self):
16+
arr= [1,2,3,7,10,19,27,77]
17+
self.assertEqual(3,binary_search(arr,7))
18+
self.assertEqual(7,binary_search(arr,77))
19+
self.assertEqual(None,binary_search(arr,8))
20+
self.assertEqual(None,binary_search(arr,-1))
21+
1522

1623
if__name__=='__main__':
1724
unittest.main()

0 commit comments

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