-
Notifications
You must be signed in to change notification settings - Fork 77
/
binary_search.py
66 lines (54 loc) · 1.9 KB
/
binary_search.py
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
# coding: utf-8
"""
Binary Search
https://en.wikipedia.org/wiki/Binary_search_algorithm
Worst-case performance: O(log n)
Best-case performance: O(1)
Average performance: O(log n)
Also see https://github.com/vinta/fuck-coding-interviews/blob/master/algorithms/searching/binary_search_left_bound.py
"""
# The following implementations cannot properly handle duplicates.
def binary_search(sorted_array, target):
low = 0
high = len(sorted_array) - 1
while low <= high:
mid = (low + high) // 2
if target == sorted_array[mid]:
return mid
elif target < sorted_array[mid]: # target is on the left side of mid.
high = mid - 1
elif target > sorted_array[mid]: # target is on the right side of mid.
low = mid + 1
return -1
def binary_search_recursive(sorted_array, target):
def binary_search_range(sorted_array, target, low, high):
# Base case
if low > high:
return -1
# Recursive case
mid = int((low + high) / 2)
mid_value = sorted_array[mid]
if target < mid_value:
return binary_search_range(sorted_array, target, low, mid - 1)
elif target > mid_value:
return binary_search_range(sorted_array, target, mid + 1, high)
else:
return mid
return binary_search_range(sorted_array, target, 0, len(sorted_array) - 1)
def binary_search_left_bound(sorted_array, target):
left = 0
right = len(sorted_array) - 1
while left <= right:
mid = (left + right) // 2
mid_value = sorted_array[mid]
if target == mid_value:
if mid > 0 and sorted_array[mid - 1] == target:
left = mid - 1
right = mid
else:
return mid
elif target < mid_value:
right = mid - 1
elif target > mid_value:
left = mid + 1
return -1