Notes
The binary search is a search algorithm that search a sorted list by repeatedly dividing the search interval in half and then apply the same rules to the desired half until the value is found or until the end of the search without a match.
Important: You must sort the list first before using the binary search.
Example
Let's search the number 5 in the sorted list below
1, 3, 3, 5, 7, 8, 8, 9, 10, 12, 16, 17, 19 Find the index of the middle number by using (low + high) // 2; In this case (0 + 12) // 2 = 6. So the middle number is at index 6 (remember the index starts from 0), which is 8.
1, 3, 3, 5, 7, 8, 8, 9, 10, 12, 16, 17, 19 Well 8 is not the number we are looking for. 5 is less than 8. So search the lower half.
1, 3, 3, 5, 7, 8, 8, 9, 10, 12, 16, 17, 19 Find the index of the middle number by using (low + high) // 2; In this case (0 + 5) // 2 = 2. So the middle number is at index 2 (remember the index starts from 0), which is 3.
1, 3, 3, 5, 7, 8, 8, 9, 10, 12, 16, 17, 19 Well 3 is not the number we are looking for. 5 is greater than 3. So search the upper remaining half.
1, 3, 3, 5, 7, 8, 8, 9, 10, 12, 16, 17, 19 Find the index of the middle number by using (low + high) // 2; In this case (3 + 5) // 2 = 4. So the middle number is at index 4 (remember the index starts from 0), which is 7.
1, 3, 3, 5, 7, 8, 8, 9, 10, 12, 16, 17, 19 Well 7 is not the number we are looking for. 5 is less than 7. So search the lower remaining half.
1, 3, 3, 5, 7, 8, 8, 9, 10, 12, 16, 17, 19 Find the index of the middle number by using (low + high) // 2; In this case (3 + 3) // 2 = 3. So the middle number is at index 3 (remember the index starts from 0), which is 5.
1, 3, 3, 5, 7, 8, 8, 9, 10, 12, 16, 17, 19 Well 5 is the number we are looking for, end search.
Sample Code in Python
def binary_search(search_list, value):
return binary_search_helper(search_list, value, 0, len(search_list)-1)
def binary_search_helper(search_list, value, low, high):
middle = (low + high) // 2
if value == search_list[middle]:
return middle
else:
if low > high:
return -1 #meaning the number cannot be found
if value < search_list[middle]:
return binary_search_helper(search_list, value, low, middle - 1)
elif value > search_list[middle]:
return binary_search_helper(search_list, value, middle + 1, high)
#Demo: Searching the number 5 in the sorted list [1, 3, 3, 5, 7, 8, 8, 9, 10, 12, 16, 17, 19]
list1 = [1, 3, 3, 5, 7, 8, 8, 9, 10, 12, 16, 17, 19]
search_num = 5
result = binary_search(list1, search_num)
if result == -1:
print("the number " + str(search_num) + " cannot be found!")
else:
print("the number " + str(search_num) + " is found at index " + str(result))