35. 搜索插入位置

转载自Leet Code

题目描述

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

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

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

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

示例 3: >输入: nums = [1,3,5,6], target = 7 >输出: 4

示例 4: >输入: nums = [1,3,5,6], target = 0 >输出: 0

示例 5:

输入: nums = [1], target = 0 输出: 0

提示:

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 为无重复元素的升序排列数组
• -104 <= target <= 104

---

我的代码

\(T(N) = O(logN)\), \(S(N) = O(1)\)

参考了Jason Li大大的这篇回答：关于二分查找的Blog（知乎）。

{.line-numbers}

class MySolution 
{
    // 查找非降序范围[first, last)内第一个不小于target的值的位置
    public int searchInsert(int[] nums, int target) 
    {
    	int first = 0; int last = nums.length;

    	while(first<last)
    	{
    		int mid = first + (last-first)/2; //防止溢出
    		if (nums[mid]<target)
    			first = mid+1;
    		else last = mid;
    	}

    	return first; // 也可以是last: 因为[first, last)为空的时候它们重合
    }
}