谁能告诉我为什么这个二进制搜索会导致我的 Macbook Pro(Monterey v12.1) 冻结？

Question

有时这段代码找到了正确的目标，而在其他目标上-它冻结了，我不知道为什么。有人可以帮忙吗？ Python3.9.7。应return指定目标。

# the result should return the index
def binarySearch(arr, target):
    left_pointer = 0
    right_pointer = len(arr) - 1
    
    while left_pointer <= right_pointer:
        mid = (left_pointer + right_pointer//2)
        
        if(arr[mid] == target):
            return mid
        if(arr[mid] < target):
            left_pointer = mid + 1
        else:
            right_pointer = mid - 1
    return -1
 
arr = [1, 2, 3, 4, 5, 6]
target = 5
result = binarySearch(arr, target)
    
if result != -1:
    print(f"the target is at index {result}")
else:
    print("The target is not in the array")
        

Answer 1

正如@stark 在评论中指出的那样，您需要更改评估“mid”的方式，从“left_pointer”和“right_pointer”。

假设，left_pointer = 7，right_pointer = 9，并且您的“目标”位于数组的索引 8 中。您计算“mid”的方式是 7 + 9//2 = 7 + 4 = 11，由于运算符的优先级，这是不正确的。检查 this 以更好地理解 python.

中的运算符优先级

工作代码：

# the result should return the index
def binarySearch(arr, target):
    left_pointer = 0
    right_pointer = len(arr) - 1
    
    while left_pointer <= right_pointer:
        mid = (left_pointer + right_pointer)//2
        
        if(arr[mid] == target):
            return mid
        if(arr[mid] < target):
            left_pointer = mid + 1
        else:
            right_pointer = mid - 1
    return -1
 
arr = [1, 2, 3, 4, 5, 6]
target = 5
result = binarySearch(arr, target)
    
if result != -1:
    print(f"the target is at index {result}")
else:
    print("The target is not in the array")