def binary_search(array, goal):
low = 0
high = len(array) - 1
while low <= high:
mid = (low + high) // 2
if goal > array[mid]:
low = mid + 1
elif goal < array[mid]:
high = mid - 1
else:
return mid
return None
my_list = [1,3,5,7,9]
print(binary_search(my_list, 3))
print(binary_search(my_list, 13))
The output result is 1 None
It's an index
Here, mid = (low+high) //2 in the while statement is the code below
def binary_search(array, goal):
low = 0
high = len(array) - 1
mid = (low + high) // 2
while low <= high:
if goal > array[mid]:
low = mid + 1
elif goal < array[mid]:
high = mid - 1
else:
return mid
return None
my_list = [1,3,5,7,9]
print(binary_search(my_list, 3))
print(binary_search(my_list, 13))
Why doesn't it work if you move it out of the door? Doesn't it matter if you're inside the door or outside?
python while-loop
Binary search is used to search for data in an ordered list.
At this point, compare with the value you want to find, and search when you narrow the search area.
Because this narrowing criterion is mid, when the value is not found, mid should be constantly updated for comparison.
Therefore, mid = (low+high) //2 must exist in the while statement.
If you take steps to make it easier to understand, it is as follows.
To find 3, set mid to 3.
Comparing array[3]5 and 3, the value you are looking for is smaller.
Narrow your search to [0]~[2].
Since the search area has become [0]~[2], mid becomes 1array[1]2 and 3, the value you are looking for is larger.
Narrow your search to [2]~[2].
Since the search area has become [2]~[2], mid will be 2array[2]3 and 3, it seems that you are looking for it.
Results found.
When comparing with the value of the mid position and finding the target by narrowing the area, Mune mid should continue to be updated within while.
© 2024 OneMinuteCode. All rights reserved.