In the above Python program to search for an element in an ordered list using binary search, the result came out true for first values that were passed in binary_Search() function because the element was present and false comes when the asked element is not present in the list.
The basic idea behind binary search is that instead of comparing the required element with all the elements of the array, we compare the required element with the middle element of the array. If it turns out to be the element we are looking for, the search is successfully. Else, if the element we are looking for is less than the middle element, it is sure that the element lies in the first or left half of the array, since the array is sorted. Similarly, if the element we are looking for is greater than the middle element, it is sure that the element lies in the second half of the array.
def binary_Search(o_list, item):
if len(o_list) == 0:
return False
else:
mid_point = len(o_list) // 2
if o_list[mid_point] == item:
return True
else:
if item < o_list[mid_point]:
return binarySearch(o_list[:mid_point], item)
else:
return binarySearch(o_list[mid_point+1:], item)
def binarySearch(a_list, item):
first = 0
last = len(a_list) - 1
found = False
while first <= last and not found:
mid_point = (first + last) // 2
if a_list[mid_point] == item:
found = True
else:
if item < a_list[mid_point]:
last = mid_point - 1
else:
first = mid_point + 1
return found
print(binary_Search([0, 4, 6, 9, 11, 19, 22, 54, 62], 6))
print(binary_Search([0, 5, 7, 14, 19, 20, 26, 34, 42], 17))
Sample Output: True False