您将获得一个无限大(或具有非常大的未知大小)的排序数组。您必须编写一段代码来打印最后一次出现的元素。
输入 输入的第一行包含表示排序数组元素的空格分隔整数。 输入的第二行代表要查找的目标元素。
限制 该数组可能有重复的元素,即元素不是严格递增的。
输出 打印目标元素的最后一次出现,否则打印 -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)
我无法处理最后一个索引中存在的元素
这里有一些问题:
在
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)
elif arr[mid] <= target: # 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)
# Return that index if that greatest value happens to be the target
return i if arr[i] == target else -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)