二进制搜索无法正常工作 (Python)

Question

我已经在 Python 中实现了二进制搜索，这是代码：

def binary_search(list, target):
    first = 0
    last = len(list) - 1

    while first <= last:
        midpoint = (first + last) // 2
        if list[midpoint] == target:
            return midpoint
        elif list[midpoint] < target:
            first = midpoint + 1
        else:
            last = midpoint - 1

    return None

我尝试使用以下代码对其进行测试：

l = ["Sam", "John", "Martha", "Garrett", "Julia"]
print(binary_search(l, "Sam"))

而且是returnsNone，而不是0。我把代码重读了一百遍也找不到错误。有人可以给我解释一下吗？

Answer 1

二分查找要求输入列表预先排序。

Answer 2

如，输入列表必须预先排序。

所以尝试使用以下代码进行测试：

l = ["Sam", "John", "Martha", "Garrett", "Julia"]
l.sort()
print(binary_search(l, "Sam"))

或者：

l = ["Sam", "John", "Martha", "Garrett", "Julia"]
print(binary_search(sorted(l), "Sam"))

Answer 3

试试下面的代码。它完美。

def binarySearch(arr, target):
    first_index = 0
    length = len(arr)
    while (first_index <= length):
        mid_point = first_index + ((length - first_index) // 2)

        res = (target == arr[mid_point])

        # Check if x is present at mid
        if (res == 0):
            return mid_point - 1

        # If x greater, ignore left half
        if (res > 0):
            first_index = mid_point + 1

        # If x is smaller, ignore right half
        else:
            length = mid_point - 1

    return None

if (result == None):
    print("Element not present")
else:
    print("Element found at index", result)

二进制搜索无法正常工作 (Python)

Binary search does not work correctly (Python)

python

algorithm

search