如何 return Python 数组中目标元素的索引？

Question

目前，当我搜索位于中点的元素时，它 returns 是正确的索引，但对于任何其他元素，它对我不起作用。

我认为我拆分数组时出错了：

    aList = [1,3,5,6,8,9,10,12,34,56,78,456]
    def recursiveBinarySearch(aList, target):
        #aList = sorted(aList)
        
        if len(aList) == 0:
            return False
        else:
            midpoint = len(aList) // 2
            if aList[midpoint] == target:
                return aList.index(target)
            else:
                if target < aList[midpoint]:
                    return recursiveBinarySearch(aList[:midpoint],target)
                else:
                    return recursiveBinarySearch(aList[midpoint+1:],target)
    
    print(recursiveBinarySearch(aList,9))

Answer 1

那是因为每次递归调用时，都会传递不同的修改列表，每次调用时索引都会改变。比如在数组的后半部分查找一个数，最终返回的值会小于len(aList)/2，因为下一次迭代只会传递这部分数组。

解决方法是传递列表的 start 和 end 点，而不是拆分列表。

aList = [1,3,5,6,8,9,10,12,34,56,78,456]
def recursiveBinarySearch(aList, target, start, end):
    #aList = sorted(aList)

    if end-start+1 <= 0:
        return False
    else:
        midpoint = start + (end - start) // 2
        if aList[midpoint] == target:
            return midpoint
        else:
            if target < aList[midpoint]:
                return recursiveBinarySearch(aList, target, start, midpoint-1)
            else:
                return recursiveBinarySearch(aList ,target, midpoint+1, end)

print(recursiveBinarySearch(aList,455, 0, len(aList)))

Answer 2

你的算法给出了最后一个拆分列表中的索引。因此，对于您的回答，如果您要打印 9 的列表，我们将得到以下内容：

[1, 3, 5, 6, 8, 9, 10, 12, 34, 56, 78, 456]
[1, 3, 5, 6, 8, 9]
[8, 9]

Wich returns 索引 1. 对于最后一个列表 [8, 9] 是正确的。这可以通过记住列表的长度轻松解决。

aList = [1,3,5,6,8,9,10,12,34,56,78,456]
def recursiveBinarySearch(aList, target, index):
    #aList = sorted(aList)
    
    if len(aList) == 0:
        return False
    else:
        midpoint = len(aList) // 2

        if aList[midpoint] == target:
            return aList.index(target)+index
        else:
            if target < aList[midpoint]:
                return recursiveBinarySearch(aList[:midpoint],target, index)
            else:
                 return recursiveBinarySearch(aList[midpoint:],target, index + midpoint)
                

print(recursiveBinarySearch(aList,56,0))

这比以前的解决方案使用的内存少一些。当然，这也更快，尽管这是微不足道的。

Answer 3

尝试编辑已接受的答案，因为它在搜索高于列表中的数字时失败，但由于某种原因 OP 不接受编辑，这意味着答案仍然错误。既然如此，我就post在这里回答。这个答案不仅修复了 IndexError 当被要求找到一个大于列表中的值时，它还将 args 更改为 kwargs 因此我们不必在每次调用时都传递它们函数

aList = [-1,1,3,5,6,8,9,10,12,34,56,78,456] 

def binary_search(arr,item,low = 0, high = None):
    if high == None:
        high = len(arr)
    mid = low + (high-low) //2  
    if high - low + 1 <= 0 or mid==high:
        return False
    else:
        guess = arr[mid]
        if guess == item:
            return mid
        if item < guess:
            return binary_search(arr, item, low, mid)
        else:
            return binary_search(arr, item, (mid+1), high)

(binary_search(aList,457))

Answer 4

我只是想分享一下我对这个问题的解决方法，看起来简单了一点：

def binary_search(array, value):
    index = int(len(array)/2) -1
    end = int(len(array)) - 1
    while array[index] != value:
        if index == end:
            return None
        elif array[index] > value:
            end = index
            index = int(index/2)
        elif array[index] < value:
            index = int((index+1 + end)/2)
    return index

Answer 5

详细解释的解决方案

二进制搜索减少了在列表中搜索项目的迭代次数。我们必须首先将第一个索引初始化为 0，将最后一个索引初始化为列表的长度 - 1。然后我们将 select 中间元素作为 (first + last)//2 现在我们必须将中间元素的值与查询元素进行比较。

如果它等于中间元素，那么我们可以return它的索引。
如果查询元素小于中间元素，那么我们会将最后一个元素更新为 mid-1。（这样我们就只能迭代列表的第一部分）
如果查询元素大于中间元素，那么我们会将第一个元素更新为 mid+1。（所以我们必须迭代列表的唯一第二部分）

下面的代码片段将清楚地说明上述语句。

aList = [-1,1,3,5,6,8,9,10,12,34,56,78,456] 

def binarySearch(numbers,item):
    first = 0 # first index
    last= len(numbers)-1 #last index
    found = False
    while( first<=last and not found):
        mid = (first + last)//2
        if numbers[mid] == item:
            found = True
            return mid
        else:            
            if item < numbers[mid]:
                last = mid - 1
            else:
                first = mid + 1 

print(binarySearch(aList,456))

注意：

由于我们在二分查找的每一步都处理掉一部分搜索情况，并在另一半上执行搜索操作，这导致最坏情况下的时间复杂度为 O(log₂N).
如果给定的列表没有排序那么我们只需要在开头对列表进行排序

Answer 6

下面是我的解决方案。

看看这个 visualization。（那里也有一个编码解决方案！）

def binary_search(input_array, value):

    low = 0
    high = len(input_array) - 1

    while low <= high:
        mid = (low + high) / 2
        if input_array[mid] == value:
            return mid
        elif input_array[mid] < value:
            low = mid + 1
        else:
            high = mid - 1

    return -1

'''

Answer 7

@Gijs Den Hollander 代码的精简版。条件被简化并且使用 midpoint 而不是 len(aList[:midpoint]) 就像我在评论中指出的那样：

def binarySearch(array, target, index=0):
    midpoint = len(array) // 2
    if array[midpoint] == target:
        return index + midpoint
    elif len(array) < 2:
        return -1
    else:
        return binarySearch(array[:midpoint], target, index) if target < array[midpoint] else binarySearch(array[midpoint:], target, midpoint+index)

Answer 8

还有一个简单的方法可以做到，

def find_index(input_list, target, sorted=False):
    print('Input list: {}'.format(input_list))

    if sorted:
        input_list.sort()
        print('Sorting Input list: {}'.format(input_list))

    try:
        index = input_list.index(target)
    except ValueError as e:
        print(e)
        index = None

    return index

而对于二分查找法，

def bsearch(il, x):
    """binary search for an input list (il)"""
    il.sort()
    print('Input list is: {}'.format(il))

    l = len(il)
    m = round(l/2)

    n = il[m]
    print("m is {} and n is {}".format(m, n))

    if n == x:
        msg = 'The number "{}" found in list index "{}"'.format(x, m)
        print(msg)
        return x
    elif x < n:
        nl = il[:m]
    elif x > n:
        nl = il[m+1:]
    elif m < 1:
        return None

    return bsearch(nl, x)

如何 return Python 数组中目标元素的索引？

How do I return the index of the target element in a Python array?

python

algorithm

binary-search