leetcode-搜索插入位置-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode-搜索插入位置。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

35. 搜索插入位置

此题使用的是二分查找

二分查找的前提条件：

1.数组是有序的；2.数组中无重复元素，一旦出现重复元素，则返回的元素下标可能不是唯一的

二分查找涉及的边界问题比较多，比如当前这道题，到底是while left < right呢还是while left <= right呢？到底是right = mid呢还是right = mid - 1呢？

在此给出个区间定义，我们知道区间有左闭右闭[left, right]，左闭右开[left, right)，左开右开(left, right)（这个是用不到的）

左闭右闭
也即[left, right]，定义的target在这个区间里，有如下两点：

1.while left <= right,此处使用的是<=，因为left== right是有意义的

2.if nums[mid] > target ,target落在了区间[left， mid），此处大家看清楚这个区间，是个右开，这个时候right的赋值应该为right = mid - 1，因为nums[mid]一定不是target

左闭右开
也即 [left, right)，定义target在这个区间里，有如下两点：

1.while left < right,此处使用的是 < ,因为left == right 在这个区间里是么有意义的

2.if nums[mid] > target,因为当前nums[mid]不等于target,去左区间继续寻找，而寻找区间是左闭右开，所以right 赋值为 right = mid

下面给出两个区间的代码，大家自己看下：
左闭右闭

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if target > nums[mid]:
                left = mid + 1
            elif target < nums[mid]:
                right = mid - 1
            else:
                return mid
        return right + 1

左闭右开文章来源地址https://www.toymoban.com/news/detail-786961.html

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums)
        while left < right:
            mid = (left + right) // 2
            if target > nums[mid]:
                left = mid + 1
            elif target < nums[mid]:
                right = mid
            else:
                return mid
        return right

到了这里，关于leetcode-搜索插入位置的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！