summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--AlgoDesignAndTechniqueEdxPython/sources/binary_search.py27
-rw-r--r--AlgoDesignAndTechniqueEdxPython/tests/binary_searchTest.py32
2 files changed, 59 insertions, 0 deletions
diff --git a/AlgoDesignAndTechniqueEdxPython/sources/binary_search.py b/AlgoDesignAndTechniqueEdxPython/sources/binary_search.py
new file mode 100644
index 0000000..5f51289
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxPython/sources/binary_search.py
@@ -0,0 +1,27 @@
+# Uses python3
+import sys
+
+def binarySearchRecursive(a, low, high, key):
+ if high < low:
+ return -1
+ mid = (int) (low + (high - low) / 2)
+ if key == a[mid]:
+ return mid
+ elif key < a[mid]:
+ return binarySearchRecursive(a, low, mid - 1, key)
+ else:
+ return binarySearchRecursive(a, mid + 1, high, key)
+
+
+def binarySearch(a, key):
+ return binarySearchRecursive(a, 0, len(a) - 1, key)
+
+if __name__ == '__main__':
+ input = sys.stdin.read()
+ data = list(map(int, input.split()))
+ n = data[0]
+ m = data[n + 1]
+ a = data[1 : n + 1]
+ for x in data[n + 2:]:
+ # replace with the call to binary_search when implemented
+ print(binarySearch(a, x), end = ' ')
diff --git a/AlgoDesignAndTechniqueEdxPython/tests/binary_searchTest.py b/AlgoDesignAndTechniqueEdxPython/tests/binary_searchTest.py
new file mode 100644
index 0000000..2ff69bc
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxPython/tests/binary_searchTest.py
@@ -0,0 +1,32 @@
+'''
+Created on Oct 8, 2018
+
+@author: haidong
+'''
+import unittest
+
+from sources.binary_search import binarySearch
+
+class Test(unittest.TestCase):
+
+
+ def test1(self):
+ a = [1, 5, 8, 12, 13]
+ self.assertEqual(2, binarySearch(a, 8))
+
+ def test2(self):
+ a = [1, 5, 8, 12, 13]
+ self.assertEqual(0, binarySearch(a, 1))
+
+ def test3(self):
+ a = [1, 5, 8, 12, 13]
+ self.assertEqual(-1, binarySearch(a, 23))
+
+ def test4(self):
+ a = [1, 5, 8, 12, 13]
+ self.assertEqual(-1, binarySearch(a, 11))
+
+
+if __name__ == "__main__":
+ #import sys;sys.argv = ['', 'Test.testName']
+ unittest.main() \ No newline at end of file