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
this disclaimer
22def 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)
Important

Use secure code every time

Secure your code as it's written. Use Snyk Code to scan source code in minutes – no build needed – and fix issues immediately. Enable Snyk Code

49def 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
34def binary_search_iterative(array, item):
35 # TODO: implement binary search iteratively here
36 pass
56def 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))
45def 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
62def 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
50def 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))
40def 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)
13def 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
182def search(self, key):
183 return self.root.search(key)

Related snippets