-
Notifications
You must be signed in to change notification settings - Fork 0
/
Binary_s_recursive_vs_iterative.py
90 lines (64 loc) · 2.24 KB
/
Binary_s_recursive_vs_iterative.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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
def recursive():
# Python Program for recursive binary search.
# Returns index of x in arr if present, else -1
def recusive_binarySearch(arr, l, r, x):
# Check base case
if r >= l:
mid = int(l + (r - l) / 2)
# If element is present at the middle itself
if arr[mid] == x:
return mid
# If element is smaller than mid, then it
# can only be present in left subarray
elif arr[mid] > x:
return recusive_binarySearch(arr, l, mid - 1, x)
# Else the element can only be present
# in right subarray
else:
return recusive_binarySearch(arr, mid + 1, r, x)
else:
# Element is not present in the array
return -1
# Test array
arr = [2, 3, 4, 10, 40]
x = 10
# Function call
result = recusive_binarySearch(arr, 0, len(arr) - 1, x)
if result != -1:
print("Element is present at index %d" % result)
else:
print("Element is not present in array")
def iterative():
############################################################
# Python code to implement iterative Binary
# Search.
# It returns location of x in given array arr
# if present, else returns -1
def iterative_binarySearch(arr, l, r, x):
while l <= r:
mid = int(l + (r - l) / 2)
# Check if x is present at mid
if arr[mid] == x:
return mid
# If x is greater, ignore left half
elif arr[mid] < x:
l = mid + 1
# If x is smaller, ignore right half
else:
r = mid - 1
# If we reach here, then the element
# was not present
return -1
# Test array
arr = [2, 3, 4, 10, 40]
x = 10
# Function call
result = iterative_binarySearch(arr, 0, len(arr) - 1, x)
if result != -1:
print("Element is present at index %d" % result)
else:
print("Element is not present in array")
if __name__ == "__main__":
a = 0
if a: recursive()
else: iterative()