Skip to content

Instantly share code, notes, and snippets.

@Momellouky
Created August 25, 2024 16:57
Show Gist options
  • Save Momellouky/85aee894ca90754b5caffb9001f27ba7 to your computer and use it in GitHub Desktop.
Save Momellouky/85aee894ca90754b5caffb9001f27ba7 to your computer and use it in GitHub Desktop.
binary search on an ordered array
def binary_search(data, param) -> bool :
found = False # To handle recursive calls
if len(data) == 0 :
return None
if len(data) == 2 :
if data[0] == param or data[1] == param :
return True
start_index = 0
end_index = len(data) - 1
middle_index = (start_index + end_index) // 2 # integer division
middle_el = data[middle_index]
if param == middle_el :
return True
if param < middle_el :
# the element resides in the first half of the array
found = binary_search(data[0:middle_index + 1], param)
else :
# The element resides in the second half of the array
found = binary_search(data[middle_index:end_index + 1], param)
return found
if __name__ == '__main__' :
# data = [ 7, 10, 3, 1, 66, 6 ]
data = [ 2, 5, 8, 10, 55, 100, 150, 300, 350, 380 ]
param = 100 # The integer we are looking for in the array
found = binary_search(data, param)
if found :
print(f"Element {param} found")
else :
print(f"Element not {param} found")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment