Characteristic
•
Input - Must use sorted list
•
Output - Index of the value
Sample Code - Iterative
# Iterative
# Time Complexity = O(log n)
# Space Complexity = O(1)
def binary_search(list, target):
first = 0
last = len(list) - 1
while first <= last:
midpoint = (first + last) // 2
if list[midpoint] == target:
return midpoint
elif list[midpoint] < target:
first = midpoint + 1
else:
last = midpoint - 1
return None
print(binary_search([1,2,3,4,5,6,7,8,9], 11))
Python
복사
Sample Code - Recursive
# Recursive
# Time Complexity = 0(log n)
# Space Complexity = O(log n)
def recursive_binary_search(list, target):
if len(list) == 0:
return False
else:
midpoint = len(list) // 2
if list[midpoint] == target:
return True
else:
if list[midpoint] < target:
return recursive_binary_search(list[midpoint+1:], target)
elif list[midpoint] > target:
return recursive_binary_search(list[:midpoint], target)
print(recursive_binary_search([1,2,3,4,5,6,7,8,9], 0))
Python
복사
