Merge pull request abranhe#17 from pieromoto/jump_search

abranhe · web-flow · commit 18e59a879e1c · 2018-10-10T21:18:23.000-04:00
Added jump search
diff --git a/allalgorithms/searches/__init__.py b/allalgorithms/searches/__init__.py
@@ -1 +1,2 @@
 from .binary_search import *
+from .jump_search import *
diff --git a/allalgorithms/searches/jump_search.py b/allalgorithms/searches/jump_search.py
@@ -0,0 +1,25 @@
+# -*- coding: UTF-8 -*-
+#
+# Jump search works for a sorted array.
+# The All ▲lgorithms library for python
+#
+# Contributed by: pieromoto
+# Github: @pieromoto
+#
+import math 
+  
+def jump_search( arr, query): 
+    arr_len = len(arr)
+    prev = 0
+    step = int(math.sqrt(arr_len))
+
+    for i in range(step-1, arr_len, step):
+        if(arr[i] >= query):
+            break
+        prev = i
+
+    for j in range(prev, arr_len):
+        if(arr[j] == query):
+            return j
+
+    return None
diff --git a/changelog.md b/changelog.md
@@ -28,3 +28,4 @@ Added:
   - Pigeonhole Sort
   - Selection Sort
   - Stooge Sort
+  - Jump Search
diff --git a/docs/readme.md b/docs/readme.md
@@ -59,6 +59,7 @@ print(binary_search(arr, 3))
 
 - ### Searches
   - [Binary Search](searches/binary-search)
+  - [Jump Search](searches/jump-search)
 - ### Sorting
   - [Bubble Sort](sorting/bubble-sort)
   - [Cocktail Shaker Sort](sorting/cocktail-shaker-sort)
diff --git a/docs/searches/jump-search.md b/docs/searches/jump-search.md
@@ -0,0 +1,36 @@
+# Jump Search
+
+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.
+
+## Install
+
+```
+pip install allalgorithms
+```
+
+## Usage
+
+```py
+from allalgorithms.searches import jump_search
+
+arr = [-2, 1, 2, 7, 10, 77]
+
+print(jump_search(arr, 7))
+# -> 3
+
+print(jump_search(arr, 3))
+# -> None
+```
+
+## API
+
+### jump_search(array, query)
+
+> Return array index if its found, otherwise returns `None`
+
+##### Params:
+
+- `arr`: Sorted Array
+- `query`: Element to search for in the array
+
+
diff --git a/readme.md b/readme.md
@@ -59,6 +59,7 @@ print(binary_search(arr, 3))
 
 - ### Searches
   - [Binary Search](https://python.allalgorithms.com/searches/binary-search)
+  - [Jump Search](https://python.allalgorithms.com/searches/jump-search)
 - ### Sorting
   - [Bubble Sort](https://python.allalgorithms.com/sorting/bubble-sort)
   - [Cocktail Shaker Sort](https://python.allalgorithms.com/sorting/cocktail-shaker-sort)
diff --git a/tests/test_searches.py b/tests/test_searches.py
@@ -1,6 +1,6 @@
 import unittest
 
-from allalgorithms.searches import binary_search
+from allalgorithms.searches import (binary_search, jump_search)
 
 
 class TestSearches(unittest.TestCase):
@@ -12,6 +12,13 @@ def test_binary_search(self):
 		self.assertEqual(None, binary_search(arr, 8))
 		self.assertEqual(None, binary_search(arr, -1))
 
+	def test_jump_search(self):
+		arr = [1, 2, 3, 7, 10, 19, 27, 77]
+		self.assertEqual(3, binary_search(arr, 7))
+		self.assertEqual(7, binary_search(arr, 77))
+		self.assertEqual(None, binary_search(arr, 8))
+		self.assertEqual(None, binary_search(arr, -1))
+
 
 if __name__ == '__main__':
 	unittest.main()

Original file line number	Diff line number	Diff line change
`@@ -1 +1,2 @@`
`1`	`1`	`from .binary_search import *`
	`2`	`+from .jump_search import *`