/
binary_search.py
52 lines (44 loc) · 1.63 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
"""
Binary Search
Find an element in a sorted array (in ascending order).
"""
# For Binary Search, T(N) = T(N/2) + O(1) // the recurrence relation
# Apply Masters Theorem for computing Run time complexity of recurrence relations:
# T(N) = aT(N/b) + f(N)
# Here,
# a = 1, b = 2 => log (a base b) = 1
# also, here
# f(N) = n^c log^k(n) // k = 0 & c = log (a base b)
# So,
# T(N) = O(N^c log^(k+1)N) = O(log(N))
def binary_search(array, query):
"""
Worst-case Complexity: O(log(n))
reference: https://en.wikipedia.org/wiki/Binary_search_algorithm
"""
low, high = 0, len(array) - 1
while low <= high:
mid = (high + low) // 2
val = array[mid]
if val == query:
return mid
if val < query:
low = mid + 1
else:
high = mid - 1
return None
#In this below function we are passing array, it's first index , last index and value to be searched
def binary_search_recur(array, low, high, val):
"""
Worst-case Complexity: O(log(n))
reference: https://en.wikipedia.org/wiki/Binary_search_algorithm
"""
#Here in Logic section first we are checking if low is greater than high which means its an error condition because low index should not move ahead of high index
if low > high:
return -1
mid = low + (high-low)//2 #This mid will not break integer range
if val < array[mid]:
return binary_search_recur(array, low, mid - 1, val) #Go search in the left subarray
if val > array[mid]:
return binary_search_recur(array, mid + 1, high, val) #Go search in the right subarray
return mid