Created
May 23, 2020 03:20
-
-
Save bobvo23/0df93837c8d354d8a627d3265fabb9ea to your computer and use it in GitHub Desktop.
udacity sample binary search
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
"""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