讨论/《二分查找》 - 二分查找模板 II/
《二分查找》 - 二分查找模板 II
共 7 个回复

不需要最后一步吧
因为 nums[right] != target 是恒成立的。
当最后 left == right 是,说明必然有 nums[left] != target

3

简化一下:
right = len(nums) - 1
最后也不用判断 left == len(nums)了

2

当 left和right 相邻时,即 left = right -1; 此时 mid == left, 如果继续执行循环,就是 nums[mid] != target, 也就是 nums[left] != target,跳出循环,就可以直接返回 -1 了。
最后一步确实多余,因为对于 right, 应该一直把它看做是数组最后一个元素的下一位置,维护好这个定义就行

nums[right] != target 不是恒成立的。。。
循环到最后一步,此时left和right相邻,接着如果执行的是right = mid,那么nums[right]就有可能等于目标值了。
所以,最后一步必不可少,而且防止数组越界也很关键。。

哦但如果input本身长度为1,那么就不会进入循环就需要后处理

确实,因为这个模版里多加了一句

        if nums[mid] == target:
            return mid

然而模版分析的例图里却没有这句,是不是搞混了

mark