无限级数最后一次出现

Question

您将获得一个无限大（或具有非常大的未知大小）的排序数组。您必须编写一段代码来打印最后一次出现的元素。

输入

输入的第一行包含空格分隔的整数，表示排序数组的元素。 输入的第二行代表要查找的目标元素。

限制

数组可能有重复的元素，即元素不是严格递增的。

输出

打印目标元素的最后一次出现，否则打印-1。

输入样本

1 2 7 7 14 19 23
7

输出示例

3

我无法处理最后一个索引中存在的元素。

def binarySearch(target,arr,start,end):
    mid = (start+end)//2
    if start>end:
        return -1
    elif arr[mid] == target:
        if arr[mid] == arr[-1]:
            return mid
        elif arr[mid+1] != target:
            return mid
        else:
            return mid+1
    elif arr[mid] > target:
        return binarySearch(target,arr,start,mid-1)
    elif arr[mid] < target:
        return binarySearch(target,arr,mid+1,end)

def finiteRange(target,arr,start,end):
    while arr[end]<target:
        start = end
        end *= 2

    return binarySearch(target,arr,start,end)

arr = list(map(int,input().split()))
target = int(input())

result = finiteRange(target,arr,0,1)
print(result)

Answer 1

对代码进行轻微修改（在注释中）以找到最后一次出现的情况，效果很好。试试这个。

import random


def binarySearch(target,arr,start,end):
    mid = (start+end)//2
    check_value = arr[mid]
    if start>end:
        return -1
    elif check_value == target:
        if arr[mid] == arr[-1] or arr[mid+1] != target:  # check if last occurrence
            return mid
        else:
            return binarySearch(target, arr, mid+1, end)  # recursive call to find last occurrence
    elif check_value > target:
        return binarySearch(target,arr,start,mid-1)
    elif check_value < target:
        return binarySearch(target,arr,mid+1,end)


def finiteRange(target,arr,start,end):
    check_val = arr[start]
    while check_val <= target:  # changed < to <= since we're searching for last occurrence
        start = end
        end *= 2
        try:
            check_val = arr[end]
        except IndexError:
            return -1
    return binarySearch(target,arr,start,end)


# original example produces correct output
arr = list(map(int,input().split()))
target = int(input())
result = finiteRange(target,arr,0,1)
print(result)
# 1 2 7 7 14 19 23
# 7
# 3

# checking with a larger array
target = 50
arr = sorted([random.randint(25, 100) for _ in range(1000)] + [target])

result = finiteRange(target,arr,0,1)
print(result)

Answer 2

这里有一些问题：

• 在

  finiteRange

  中，没有检查

  end

  是否为有效索引，即

  arr[end]

  可能会引发异常。例如，检查输入 [1, 2, 3, 7] 和目标 7。当您指示不允许使用

  len

  时，那么您应该捕获错误并仍然调用

  binarySearch

• 在

  finiteRange

  中，循环条件有

  arr[end] < target

  ，这也意味着如果这两个相等，则循环退出，但是您可能会错过

  arr[end+1]

  也可能等于目标的事实，并且拨打

  binarySearch

  的电话将会错过。

• 不是问题，但由于

  finiteRange

  仅被调用一次，因此它不应该将

  start

  和

  end

  作为参数。相反，这些可以在函数本身中初始化。

• 如果在

  binarySearch

  中，您在索引

  mid

  处找到了目标，并且发现该目标也在列表末尾找到，您仍然返回

  mid

  ，而

  mid

  可能不是该目标的索引列表中的最后一个元素。此外，如果不允许您使用

  len

  ，那么我会假设

  arr[-1]

  也不被允许。更重要的是，这个 last 条目的索引可能比

  end

  大得多，但您的二分搜索应该只考虑范围

  start

  -

  end

  。

• 当您发现索引

  mid

  和

  mid+1

  处的值都是目标值时，您会执行

  return mid+1

  而无需检查该目标值是否也存在于索引

  mid+2

  处，...等

这个想法是，当您发现左侧值等于目标时，您也会从左侧缩小窗口：二分搜索应该继续。仅当窗口变空时，您才应将其视为基本情况并返回。在这种情况下，如果目标值存在于列表中，则保证

end

索引就是我们需要的。如果列表中不存在，则由 caller（即

finiteRange

）检测并返回 -1。

这是更正后的代码：

def binarySearch(target, arr, start, end):
    mid = (start + end) // 2
    if start > end:
        return end
    try:  # Trap the error when `mid` is out of range
        if arr[mid] > target:
            return binarySearch(target, arr, start, mid-1)
        else: # Narrow the search also when the target is found
            return binarySearch(target, arr, mid+1, end)
    except IndexError:  # If `mid` is out of range, we go "left"
        return binarySearch(target, arr, start, mid-1)

def finiteRange(target, arr):
    start = 0  # start/end don't need to be parameters
    end = 1
    try:  # Trap the error when accessing an out of range index
        while arr[end] <= target:  # Continue when equal too
            start = end
            end *= 2
    except IndexError:
        pass  # In this case we stop moving the range
    # Use recursion to find the last index of the greatest value
    #  that is not greater than the target
    i = binarySearch(target, arr, 0, end - 1)
    try:
        # Return that index if that greatest value happens to be the target
        return i if arr[i] == target else -1
    except IndexError: # This happens when the list is empty
        return -1

调用示例：

arr = [1, 2, 3, 8, 9, 9, 10, 10, 10, 10, 11, 12, 13, 13]
target = 13
result = finiteRange(target, arr)  # Don't pass 0 and 1 as arguments
print(result)