leetcode-035-搜索插入位置

题目及测试

package pid035;
/*35. 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。请必须使用时间复杂度为 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提示:1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 为 无重复元素 的 升序 排列数组
-104 <= target <= 104
*/public class main {public static void main(String[] args) {int[][] testTable = {{1,3,5,6},{1,2,5,6},{1,5,5,6},{2,4,5,6}};for (int[] ito : testTable) {test(ito,3);}}private static void test(int[] ito,int k) {Solution solution = new Solution();int rtn;long begin = System.currentTimeMillis();for (int i = 0; i < ito.length; i++) {System.out.print(ito[i]+" ");		    }System.out.println();//开始时打印数组rtn = solution.searchInsert(ito,k);//执行程序long end = System.currentTimeMillis();	//System.out.println(ito + ": rtn=" + rtn);System.out.println("rtn=" +rtn);System.out.println();System.out.println("耗时：" + (end - begin) + "ms");System.out.println("-------------------");}}

解法1（成功，0ms，极快）

1 题目要找的元素是：第一个大于等于 target 的元素的下标；
2 数组的长度 len 也有可能是问题的答案，「参考代码 2」设置 right = len 不是因为设置区间是「左闭右开」，而是因为 len 本来就有可能是问题的答案。
上面 2 个小点，都需要仔细分析题意和几个示例得到，任何模板都不能回答这样的问题。

根据示例，分析题目要我们返回的「插入元素的位置」是什么。
根据「示例 3」：
输入: [1, 3, 5, 6], 7
输出: 4
我们知道：如果目标元素 严格大于 输入数组中的最后一个元素，题目需要我们返回数组的最后一个元素的下标 +1（也就是数组的长度）。

又根据「示例 2」：
输入: [1, 3, 5, 6], 2
输出: 1
我们知道：题目要我们返回第 1 个 大于等于 目标元素 2 的下标（分析出这一点非常重要），因此返回 1。等于的情况可以看「示例 1」。

思路分析
在有序数组中查找，可以使用「二分查找」。
根据「题意分析」中对示例的描述：

情况 1：如果当前 mid 看到的数值严格小于 target，那么 mid 以及 mid 左边的所有元素就一定不是「插入元素的位置」，因此下一轮搜索区间是 [mid + 1..right]，下一轮把 left 移动到 mid + 1 位置，因此设置 left = mid + 1；
情况 2：否则，如果 mid 看到的数值大于等于 target，那么 mid 可能是「插入元素的位置」，mid 的右边一定不存在「插入元素的位置」。如果 mid 的左边不存在「插入元素的位置」，我们才可以说 mid 是「插入元素的位置」。因此下一轮搜索区间是 [left..mid]，下一轮把 right 移动到 mid 位置，因此设置 right = mid。
说明：上面的两点中，「情况 2」其实不用分析得那么细致， 因为只要「情况 1」的区间分析是正确的，「情况 2」一定是「情况 1」得到的区间的反面区间。
说明：while (left < right) 表示当 left 与 right 重合的时候，搜索终止。根据题意和示例，区间 nums[left..right] 里一定存在「插入元素的位置」，且 while 循环里只把区间分成两个部分，退出循环的时候一定有 left == right 成立，因此返回 left 或者 right 都可以。

既然 len 也有可能是答案，可以在初始化的时候，把 right 设置成 len，在一开始的时候就不需要特殊判断了。
 

package pid035;
class Solution {public int searchInsert(int[] nums, int target) {int length = nums.length;if(length == 0){return 0;}if(target <= nums[0]){return 0;}if(target == nums[length-1]){return length-1;}if(target > nums[length-1]){return length;}int begin = 0;int end = length;int mid = 0;while(begin<end){mid = (begin+end)/2;if(nums[mid] == target){return mid;}if(nums[mid] < target){begin = mid+1;}if(nums[mid] > target){end = mid;}}return begin;}
}