python - 二分查找元素的最低索引

Question

我想实现一个二分搜索函数，它返回要搜索的元素的最低索引。这是我的代码:

def binarySearch(arr,x):
    n=len(arr)
    if n==1:
        if arr[0]==x:
            return 0
        else:
            return -1 # not in list
    else:
        m=int(n/2)
        if x <= arr[m]:
            return binarySearch(arr[:m],x)
        else:
            return m+binarySearch(arr[m+1:],x)

但是，这不能正常工作。有人可以帮助我吗？

Answer 1

def binarySearch(arr,x):

    if len(arr) == 0:
        return 0

    else:
        m=int(len(arr)/2)

        if arr[m] == x:
            c = 1

            while arr[m-c] == x:
                c += 1
            return m-c+1

        else:
            if x < arr[m]:
                return binarySearch(arr[:m],x)
            else:
                return binarySearch(arr[m+1:],x)

这可以解决您的问题，同时也为您提供最低的索引