Skip to content

Instantly share code, notes, and snippets.

@bobvo23
Created May 23, 2020 03:20
Show Gist options
  • Save bobvo23/0df93837c8d354d8a627d3265fabb9ea to your computer and use it in GitHub Desktop.
Save bobvo23/0df93837c8d354d8a627d3265fabb9ea to your computer and use it in GitHub Desktop.
udacity sample binary search
"""You're going to write a binary search function.
You should use an iterative approach - meaning
using loops.
Your function should take two inputs:
a Python list to search through, and the value
you're searching for.
Assume the list only has distinct elements,
meaning there are no repeated values, and
elements are in a strictly increasing order.
Return the index of value, or -1 if the value
doesn't exist in the list."""
current_idx = 0
def binary_search(input_array, value):
lower = 0
upper = len (input_array)-1
while (upper >= lower):
mid_idx = (upper+lower)//2
if input_array[mid_idx]< value:
lower = mid_idx+1
elif input_array[mid_idx]==value:
return mid_idx
else:
if lower == upper:
return -1
upper = mid_idx
test_list = [1,3,9,11,15,19,29]
test_val1 = 25
test_val2 = 15
print (binary_search(test_list, test_val1))
print (binary_search(test_list, test_val2))
print("haha")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment