10 examples of 'python program to implement binary search without recursion.' in Python

Every line of 'python program to implement binary search without recursion.' code snippets is scanned for vulnerabilities by our powerful machine learning engine that combs millions of open source libraries, ensuring your Python code is secure.

All examples are scanned by Snyk Code

By copying the Snyk Code Snippets you agree to
 22 def binary_search_recur(arr, val): 23 if arr is None or len(arr) == 0: 24 return False 25 mid = len(arr)/2 26 if arr[mid] == val: 27 return True 28 elif arr[mid] > val: 29 return binary_search_recur(arr[:mid], val) 30 else: 31 return binary_search_recur(arr[mid+1:], val)
 49 def binary_search_1(left, right): 50 # 如果选择右中位数，当区间只剩下 2 个元素的时候， 51 # 一旦进入 right = mid 这个分支，右边界不会收缩，代码进入死循环 52 while left < right: 53 # 选择左中位数 54 # mid = left + (right - left) // 2 55 # left 和 right 一般都表示索引，使用 + 且无符号右移，在 left 和 right 都很大的时候，虽然整形溢出，但结果正确 56 # 在 Java 中使用 `int mid = (left + right) >>> 1;` ，一定是无符号右移 57 mid = (left + right) >> 1 58 if check(mid): 59 # 先写可以排除中位数的逻辑 60 left = mid + 1 61 else: 62 # 右边界不能排除，这半边逻辑不用记 63 # 逻辑是：上一个分支的另一个边界收缩，但不排除中位数 64 right = mid
 34 def binary_search_iterative(array, item): 35 # TODO: implement binary search iteratively here 36 pass
 56 def test_list_size_2_does_not_exist(self): 57 self.assertEqual(linear_search([3, 5], 7), -1) 58 self.assertEqual(binary_search_iteratively([3, 5], 7), -1) 59 self.assertEqual(binary_search_recursively_in_place([3, 5], 7), -1) 60 self.assertFalse(binary_search_recursively_not_in_place([3, 5], 7))
 45 def search(self,key,node = None): 46 47 if node is None: 48 node = self.root 49 50 if self.root.key == key: 51 print "key is at the root" 52 return self.root 53 54 else: 55 if node.key == key : 56 print "key exists" 57 return node 58 59 elif key < node.key and node.left is not None: 60 print "left" 61 return self.search(key,node = node.left) 62 63 elif key > node.key and node.right is not None: 64 print "right" 65 return self.search(key,node = node.right) 66 67 else: 68 print "key does not exist" 69 return None
 62 def binary_search(seq, t, key=None, cmp=None): # bisect module doesn't support key/compare callbacks 63 # http://code.activestate.com/recipes/81188-binary-search/ 64 min = 0 65 max = len(seq) - 1 66 if not (cmp or key): 67 while True: 68 if max < min: return -1 69 m = (min + max) // 2 70 k = seq[m] 71 if k < t: min = m + 1 72 elif k > t: max = m - 1 73 else: return m 74 elif key: 75 t = key(t) 76 while True: 77 if max < min: return -1 78 m = (min + max) // 2 79 k = key(seq[m]) 80 if k < t: min = m + 1 81 elif k > t: max = m - 1 82 else: return m 83 else: 84 while True: 85 if max < min: return -1 86 m = (min + max) // 2 87 s = cmp(seq[m], t) 88 if s < 0: min = m + 1 89 elif s > 0: max = m - 1 90 else: return m
 50 def test_list_size_2_exists_second_place(self): 51 self.assertEqual(linear_search([3, 5], 5), 1) 52 self.assertEqual(binary_search_iteratively([3, 5], 5), 1) 53 self.assertEqual(binary_search_recursively_in_place([3, 5], 5), 1) 54 self.assertTrue(binary_search_recursively_not_in_place([3, 5], 5))
 40 def recursive_search(self, node, data): 41 if node is None: 42 return None 43 44 if node.data == data: 45 return node 46 47 if data > node.data: 48 self.recursive_search(node.right, data) 49 else: 50 self.recursive_search(node.left, data)
 13 def binary_search(array, query): 14 lo, hi = 0, len(array) - 1 15 while lo <= hi: 16 mid = lo + (hi - lo) // 2 17 val = array[mid] 18 19 # If the element is present at the middle itself 20 21 if val == query: 22 return mid 23 24 # If element is smaller than mid, then 25 # it can only be present in right subarray 26 27 elif val < query: 28 lo = mid + 1 29 30 # Else the element can only be present 31 # in left subarray 32 33 else: 34 hi = mid - 1 35 36 # We reach here when element is not 37 # present in array 38 39 return None
 182 def search(self, key): 183 return self.root.search(key)