搜索插入位置

题目链接

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例:

输入: nums = [1,3,5,6], target = 5
输出: 2

思路

解法一：

采用左闭右开的方式，分为四种情况

  1. 目标值在数组所有元素之前
  2. 目标值等于数组中的某一个元素
  3. 目标值插入数组中的某个位置
  4. 目标值在数组所有元素之后
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)
        while left < right:
            mid = left + (right -left) // 2
            if nums[mid] == target: # 找到target，直接返回
                return mid 
            elif nums[mid] < target: # target在右区间[mid + 1, right)
                left = mid + 1
            else: # target在左区间[left, mid)
                right = mid
        # 分别处理如下四种情况
        # 目标值在数组所有元素之前 [0,0)
        # 目标值等于数组中某一个元素 return middle,即right
        # 目标值插入数组中的位置 [left, right) ，return right 即可
        # 目标值在数组所有元素之后的情况 [left, right)，return right 即可
        return right