Repository navigation
Expand file tree
/
Copy pathbinary_search.py
More file actions
42 lines (32 loc) · 1.55 KB
/
Copy pathbinary_search.py
File metadata and controls
42 lines (32 loc) · 1.55 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
"""Binary Search
Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval
covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow
the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or
the interval is empty.
"""
def binary_search_iterative(array: list[int], target: int) -> int | None:
"""Narrow the [left, right] bounds by half each iteration until target is found or the bounds cross."""
left = 0
right = len(array) - 1
while left <= right:
middle = (left + right) // 2
if array[middle] == target:
return middle
if array[middle] < target:
left = middle + 1
elif array[middle] > target:
right = middle - 1
return None
def binary_search_recursive(array: list[int], left: int, right: int, target: int) -> int | None:
"""Recurse into the left or right sub-array each call until target is found or the bounds cross."""
if right >= left:
mid = (left + right) // 2
# If element is present at the middle
if array[mid] == target:
return mid
# If element is smaller than mid, then it can only be present in left sub-array
if array[mid] > target:
return binary_search_recursive(array, left, mid - 1, target)
# Else the element can only be present in the right sub-array
return binary_search_recursive(array, mid + 1, right, target)
return None