題目及測(cè)試

package pid035;
/*35. 搜索插入位置
給定一個(gè)排序數(shù)組和一個(gè)目標(biāo)值，在數(shù)組中找到目標(biāo)值，并返回其索引。如果目標(biāo)值不存在于數(shù)組中，返回它將會(huì)被按順序插入的位置。請(qǐng)必須使用時(shí)間復(fù)雜度為 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 為 無重復(fù)元素 的 升序 排列數(shù)組
-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();//開始時(shí)打印數(shù)組rtn = solution.searchInsert(ito,k);//執(zhí)行程序long end = System.currentTimeMillis();	//System.out.println(ito + ": rtn=" + rtn);System.out.println("rtn=" +rtn);System.out.println();System.out.println("耗時(shí)：" + (end - begin) + "ms");System.out.println("-------------------");}}

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

1 題目要找的元素是：第一個(gè)大于等于 target 的元素的下標(biāo)；
2 數(shù)組的長(zhǎng)度 len 也有可能是問題的答案，「參考代碼 2」設(shè)置 right = len 不是因?yàn)樵O(shè)置區(qū)間是「左閉右開」，而是因?yàn)?len 本來就有可能是問題的答案。
上面 2 個(gè)小點(diǎn)，都需要仔細(xì)分析題意和幾個(gè)示例得到，任何模板都不能回答這樣的問題。

根據(jù)示例，分析題目要我們返回的「插入元素的位置」是什么。
根據(jù)「示例 3」：
輸入: [1, 3, 5, 6], 7
輸出: 4
我們知道：如果目標(biāo)元素 嚴(yán)格大于 輸入數(shù)組中的最后一個(gè)元素，題目需要我們返回?cái)?shù)組的最后一個(gè)元素的下標(biāo) +1（也就是數(shù)組的長(zhǎng)度）。

又根據(jù)「示例 2」：
輸入: [1, 3, 5, 6], 2
輸出: 1
我們知道：題目要我們返回第 1 個(gè) 大于等于 目標(biāo)元素 2 的下標(biāo)（分析出這一點(diǎn)非常重要），因此返回 1。等于的情況可以看「示例 1」。

思路分析
在有序數(shù)組中查找，可以使用「二分查找」。
根據(jù)「題意分析」中對(duì)示例的描述：

情況 1：如果當(dāng)前 mid 看到的數(shù)值嚴(yán)格小于 target，那么 mid 以及 mid 左邊的所有元素就一定不是「插入元素的位置」，因此下一輪搜索區(qū)間是 [mid + 1..right]，下一輪把 left 移動(dòng)到 mid + 1 位置，因此設(shè)置 left = mid + 1；
情況 2：否則，如果 mid 看到的數(shù)值大于等于 target，那么 mid 可能是「插入元素的位置」，mid 的右邊一定不存在「插入元素的位置」。如果 mid 的左邊不存在「插入元素的位置」，我們才可以說 mid 是「插入元素的位置」。因此下一輪搜索區(qū)間是 [left..mid]，下一輪把 right 移動(dòng)到 mid 位置，因此設(shè)置 right = mid。
說明：上面的兩點(diǎn)中，「情況 2」其實(shí)不用分析得那么細(xì)致， 因?yàn)橹灰盖闆r 1」的區(qū)間分析是正確的，「情況 2」一定是「情況 1」得到的區(qū)間的反面區(qū)間。
說明：while (left < right) 表示當(dāng) left 與 right 重合的時(shí)候，搜索終止。根據(jù)題意和示例，區(qū)間 nums[left..right] 里一定存在「插入元素的位置」，且 while 循環(huán)里只把區(qū)間分成兩個(gè)部分，退出循環(huán)的時(shí)候一定有 left == right 成立，因此返回 left 或者 right 都可以。

既然 len 也有可能是答案，可以在初始化的時(shí)候，把 right 設(shè)置成 len，在一開始的時(shí)候就不需要特殊判斷了。
?

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;}
}