如何返回 Python 数组中目标元素的索引？_python

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

我想我在拆分数组时犯了一个错误：

    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))

那是因为每次进行递归调用时，都会传递一个不同的修改列表，并且每次调用时索引都会更改。 例如，如果在数组的后半部分搜索一个数字，则最终返回的值将小于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)))

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

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

Wich 返回索引 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))

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

尝试编辑接受的答案，因为它在搜索高于列表中的数字时失败，但由于某种原因 OP 不接受编辑，这意味着答案仍然是错误的。 既然如此，我将在这里发布答案。 当被要求查找不在列表中的大于 1 的值时，此答案不仅修复了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))

我只是想分享我对这个问题的解决方案，似乎更简单一点：

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

详细解释的解决方案

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

如果它等于中间元素，那么我们可以按原样返回它的索引。
如果查询元素小于中间元素，那么我们会将最后一个元素更新为 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)。
如果给定的列表没有排序，那么我们只需要在开始时对列表进行排序

下面是我的解决方案。

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

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

'''

@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)

另一种简单的方法可以做到，

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)

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

问题描述

1楼

2楼

3楼

4楼

5楼

6楼

7楼

8楼