2. Binary Search
Binary Search¶
In [1]:
Copied!
arr = [1, 5, 8, 9, 11, 13, 15, 19, 21]
arr = [1, 7, 5, 9, 2, 12, 3]
target = 14
arr = [1, 5, 8, 9, 11, 13, 15, 19, 21]
arr = [1, 7, 5, 9, 2, 12, 3]
target = 14
In [2]:
Copied!
def binary_search(arr, target):
mid = len(arr) // 2
# base case
if arr[mid] == target:
print("target: {} ==> Found".format(target))
return True
elif len(arr) <= 1:
print("target: {} ==> Not Found".format(target))
return False
if target < arr[mid]:
binary_search(arr[:mid], target)
elif target > arr[mid]:
binary_search(arr[mid:], target)
def binary_search(arr, target):
mid = len(arr) // 2
# base case
if arr[mid] == target:
print("target: {} ==> Found".format(target))
return True
elif len(arr) <= 1:
print("target: {} ==> Not Found".format(target))
return False
if target < arr[mid]:
binary_search(arr[:mid], target)
elif target > arr[mid]:
binary_search(arr[mid:], target)
In [3]:
Copied!
for i in range(0, 25):
binary_search(arr, i)
for i in range(0, 25):
binary_search(arr, i)
target: 0 ==> Not Found target: 1 ==> Found target: 2 ==> Not Found target: 3 ==> Not Found target: 4 ==> Not Found target: 5 ==> Found target: 6 ==> Not Found target: 7 ==> Not Found target: 8 ==> Found target: 9 ==> Found target: 10 ==> Not Found target: 11 ==> Found target: 12 ==> Not Found target: 13 ==> Found target: 14 ==> Not Found target: 15 ==> Found target: 16 ==> Not Found target: 17 ==> Not Found target: 18 ==> Not Found target: 19 ==> Found target: 20 ==> Not Found target: 21 ==> Found target: 22 ==> Not Found target: 23 ==> Not Found target: 24 ==> Not Found
In [4]:
Copied!
In [5]:
Copied!
def binary_search_idx(arr, target, low, high):
if low > high:
return -1
mid = (low + high) // 2
if target == arr[mid]:
return mid
if target < arr[mid]:
binary_search_idx(arr, target, low, mid - 1)
elif target > arr[mid]:
binary_search_idx(arr, target, mid + 1, high)
def binary_search_idx(arr, target, low, high):
if low > high:
return -1
mid = (low + high) // 2
if target == arr[mid]:
return mid
if target < arr[mid]:
binary_search_idx(arr, target, low, mid - 1)
elif target > arr[mid]:
binary_search_idx(arr, target, mid + 1, high)
In [6]:
Copied!
for i in arr:
print(binary_search_idx(arr, i, 0, len(arr) - 1))
for i in arr:
print(binary_search_idx(arr, i, 0, len(arr) - 1))
None None None 3 None None None
In [7]:
Copied!
def binary_search_recursive(array, element, start, end):
if start > end:
return -1
mid = (start + end) // 2
if element == array[mid]:
return mid
if element < array[mid]:
return binary_search_recursive(array, element, start, mid - 1)
else:
return binary_search_recursive(array, element, mid + 1, end)
def binary_search_recursive(array, element, start, end):
if start > end:
return -1
mid = (start + end) // 2
if element == array[mid]:
return mid
if element < array[mid]:
return binary_search_recursive(array, element, start, mid - 1)
else:
return binary_search_recursive(array, element, mid + 1, end)
In [8]:
Copied!
for i in arr:
print(binary_search_recursive(arr, i, 0, len(arr) - 1))
for i in arr:
print(binary_search_recursive(arr, i, 0, len(arr) - 1))
0 1 -1 3 -1 5 -1
In [ ]:
Copied!