二分搜索方法并不适用于所有情况

Question

我正在尝试做一道 LeetCode 题：

给定一个按升序排序的整数数组 nums 和一个整数目标，编写一个函数在 nums 中搜索目标。如果目标存在，则返回其索引。否则，返回-1。

您必须编写一个运行时间复杂度为 O(log n) 的算法。

我尝试利用每个子数组的中间索引之间的偏移差来使用递归来解决该问题。然而，在每种情况下，都有另一种情况导致代码失败。有什么想法吗？

def binary(nums, target, answer):
    n = len(nums)  

    if len(nums) == 1 and nums[0] != target: 
        #special case where the subarray is length one and it doesnt match the target
        return -1 

    if nums[n // 2] == target:
        return answer
    elif nums[n // 2] > target:
        answer = binary(nums[:n // 2], target, answer)
    else:
        answer = binary(nums[n // 2 + 1:], target, answer+(n // 2) + 1)

    return answer

class Solution(object):
    def search(self, nums, target):
        #Adjusting the offset in the beginning
        if nums[0] == target:
            return 0
        elif nums[len(nums) // 2] >= target:
            return binary(nums, target, len(nums) // 2)
        else:
            return binary(nums, target, 0)

Answer 1

不需要递归。诀窍是在

+ 1

值可能仍然存在的剩余范围内维持下限和上限 (

target

)。在每次迭代中，查看范围的“中间”（median，虽然不是统计意义）。如果其值高于

target

，则将其设为

upper

界限。如果低于目标，则将其设为

lower

界限 (

+ 1

)。最后剩下的可能性是您已经找到了

target

。如果 [

lower

,

upper

) 区间崩溃，则找不到

target

。

唯一令人惊讶的一点可能是

lower = current + 1

与

upper = current

，但考虑到

upper

具有“过去的结束”含义（就像在

range(lower, upper)

中那样），这应该不足为奇。

def search(nums, target):
  lower, upper = 0, len(nums)
  while lower < upper:
    current = (lower + upper) // 2
    if nums[current] < target:
      lower = current + 1
    elif nums[current] > target:
      upper = current
    else:
      return current
  return -1