题目描述

• 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
• 你可以假设数组中无重复元素。

示例 1:

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

示例 2:

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

示例 3:

输入: [1,3,5,6], 7
输出: 4

示例 4:

输入: [1,3,5,6], 0
输出: 0

答题

解题思路：
二分查找，用key在判断条件中记录小于target的当前最大值

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        start, end = 0, len(nums)-1
        while start < end:
            mid = (start+end)/2
            if nums[mid] < target:
                start = mid + 1
            elif nums[mid] > target:
                end = mid - 1
            else:
                return mid
        if target == nums[start]:
            return start
        elif target < nums[start]:
            return max(0, start)
        else:
            return start+1

class Solution:
    def searchInsert(self, nums, target):
        length = len(nums)
        # 这里不单独判断目标值可能会被插入末尾的情况，统一进行判断
        # 设定边界
        left = 0
        # 因为目标值可能会被插入末尾，所以右边界设为 length
        right = length

        while left < right:
            # 开始进行二分查找
            # 这里是向下取整，mid 是包含在 [left, mid] 中的
            mid = left + (right - left) // 2
            # 严格小于 target 的元素，一定不是解
            if nums[mid] < target:
                left = mid + 1
            elif nums[mid] == target:
                # 当数组存在与目标值相同的元素时，返回其索引
                return mid
            else:
                right = mid
        
        return left