Merge pull request keon#753 from DivyanshMandhan/master

ankit167 · web-flow · commit 40f240a46573 · 2021-02-06T19:52:14.000+05:30
add ternary search
diff --git a/algorithms/search/__init__.py b/algorithms/search/__init__.py
@@ -1,4 +1,5 @@
 from .binary_search import *
+from .ternary_search import *
 from .first_occurrence import *
 from .last_occurrence import *
 from .linear_search import *
diff --git a/algorithms/search/ternary_search.py b/algorithms/search/ternary_search.py
@@ -0,0 +1,37 @@
+"""
+Ternary search is a divide and conquer algorithm that can be used to find an element in an array. 
+It is similar to binary search where we divide the array into two parts but in this algorithm, 
+we divide the given array into three parts and determine which has the key (searched element). 
+We can divide the array into three parts by taking mid1 and mid2.
+Initially, l and r will be equal to 0 and n-1 respectively, where n is the length of the array.
+mid1 = l + (r-l)/3 
+mid2 = r – (r-l)/3 
+
+Note: Array needs to be sorted to perform ternary search on it.
+T(N) = O(log3(N))
+log3 = log base 3
+"""
+def ternary_search(l, r, key, arr):
+	while r >= l:
+		
+		mid1 = l + (r-l) // 3
+		mid2 = r - (r-l) // 3
+
+		if key == arr[mid1]:
+			return mid1
+		if key == mid2:
+			return mid2
+
+		if key < arr[mid1]:
+            # key lies between l and mid1
+			r = mid1 - 1
+		elif key > arr[mid2]:
+            # key lies between mid2 and r
+			l = mid2 + 1
+		else:
+            # key lies between mid1 and mid2
+			l = mid1 + 1
+			r = mid2 - 1
+
+    # key not found 
+	return -1
diff --git a/tests/test_search.py b/tests/test_search.py
@@ -1,5 +1,6 @@
 from algorithms.search import (
     binary_search, binary_search_recur,
+    ternary_search,
     first_occurrence,
     last_occurrence,
     linear_search,
@@ -41,6 +42,15 @@ def test_binary_search(self):
         self.assertEqual(11, binary_search_recur(array, 0, 11, 6))
         self.assertEqual(-1, binary_search_recur(array, 0, 11, 7))
         self.assertEqual(-1, binary_search_recur(array, 0, 11, -1))
+    
+    def test_ternary_search(self):
+        array = [1, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 6]
+        self.assertEqual(10, ternary_search(0, 11, 5, array))
+        self.assertEqual(3, ternary_search(0, 10, 3, array))
+        self.assertEqual(-1, ternary_search(0, 10, 5, array))
+        self.assertEqual(-1, ternary_search(0, 11, 7, array))
+        self.assertEqual(-1, ternary_search(0, 11, -1, array))
+        
 
     def test_last_occurrence(self):
         array = [1, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 6, 6, 6]

Original file line number	Diff line number	Diff line change
`@@ -1,4 +1,5 @@`
`1`	`1`	`from .binary_search import *`
	`2`	`+from .ternary_search import *`
`2`	`3`	`from .first_occurrence import *`
`3`	`4`	`from .last_occurrence import *`
`4`	`5`	`from .linear_search import *`