Binary Search using Python
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
def binary_search(a_list, search_item): | |
""" | |
Binary search using loop on a sorted list | |
Based on the value we look for, bifurcate the list into two look up windows. | |
The value we look for is the middle value of current window. | |
If search value < middle value of the window, put the upper bound to middle value | |
If search value > middle value of the window, put the lower bound to middle value | |
If search value == middle value of the window, item is found. | |
If lower bound > upper bound, the list limits are out of index. We can stop the search. | |
""" | |
low = 0 | |
high = len(a_list) - 1 | |
while low <= high: | |
mid = (high+low)//2 | |
if a_list[mid] == search_item: | |
return mid + 1 | |
else: | |
if search_item > a_list[mid]: | |
low = mid + 1 | |
else: | |
high = mid - 1 | |
return -1 | |
def binary_search2(a_list, search_item, low, high): | |
""" | |
Binary search using recursion | |
""" | |
if low <= high: | |
mid = (high+low)//2 | |
if a_list[mid] == search_item: | |
return mid + 1 | |
else: | |
if search_item > a_list[mid]: | |
return binary_search2(a_list, search_item, mid+1, high) | |
else: | |
return binary_search2(a_list, search_item, low, mid - 1) | |
return -1 | |
# a_list = [1, -2,3,4,5] | |
# search_item = 4 | |
# print(binary_search2(a_list, search_item, 0, len(a_list)-1)) | |
# search_item = 5 | |
# print(binary_search2(a_list, search_item, 0, len(a_list))) | |
# search_item = 2 | |
# print(binary_search2(a_list, search_item, 0, len(a_list))) | |
# search_item = -1 | |
# print(binary_search2(a_list, search_item, 0, len(a_list))) | |
# search_item = 8 | |
# print(binary_search2(a_list, search_item, 0, len(a_list)-1)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment