給定一個(gè)排序數(shù)組和一個(gè)目標(biāo)值，在數(shù)組中找到目標(biāo)值党涕，并返回其索引。如果目標(biāo)值不存在于數(shù)組中巡社，返回它將會(huì)被按順序插入的位置膛堤。你可以假設(shè)數(shù)組中無(wú)重復(fù)元素。
示例 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
解題思路
題目告訴你“排序數(shù)組”晌该，其實(shí)就是在暗示你用二分查找法, 二分查找法的思想并不難肥荔，但寫(xiě)好一個(gè)二分法并不簡(jiǎn)單。
public class Solution3 {
public int searchInsert(int[] nums, int target) {
int len = nums.length;
if (nums[len - 1] < target) {
return len;
}
int left = 0;
int right = len - 1;
while (left <= right) {
int mid = (left + right) / 2;
// 等于的情況最簡(jiǎn)單朝群，我們應(yīng)該放在第 1 個(gè)分支進(jìn)行判斷
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
// 題目要我們返回大于或者等于目標(biāo)值的第 1 個(gè)數(shù)的索引
// 此時(shí) mid 一定不是所求的左邊界燕耿，
// 此時(shí)左邊界更新為 mid + 1
left = mid + 1;
} else {
// 既然不會(huì)等于，此時(shí) nums[mid] > target
// mid 也一定不是所求的右邊界
// 此時(shí)右邊界更新為 mid - 1
right = mid - 1;
}
}
// 注意：一定得返回左邊界 left姜胖，
// 如果返回右邊界 right 提交代碼不會(huì)通過(guò)
// 【注意】下面我嘗試說(shuō)明一下理由誉帅，如果你不太理解下面我說(shuō)的，那是我表達(dá)的問(wèn)題
// 但我建議你不要糾結(jié)這個(gè)問(wèn)題，因?yàn)槲覍⒁榻B的二分查找法模板蚜锨，可以避免對(duì)返回 left 和 right 的討論
// 理由是對(duì)于 [1,3,5,6]档插，target = 2，返回大于等于 target 的第 1 個(gè)數(shù)的索引亚再，此時(shí)應(yīng)該返回 1
// 在上面的 while (left <= right) 退出循環(huán)以后郭膛，right < left，right = 0 氛悬，left = 1
// 根據(jù)題意應(yīng)該返回 left则剃，
// 如果題目要求你返回小于等于 target 的所有數(shù)里最大的那個(gè)索引值，應(yīng)該返回 right
return left;
}
}
Java
int mid = (left + right) / 2
這行代碼是有問(wèn)題的如捅，在 left 和 right 都比較大的時(shí)候棍现，left + right 很有可能超過(guò) int 類型能表示的最大值，即整型溢出伪朽，為了避免這個(gè)問(wèn)題轴咱，應(yīng)該寫(xiě)成：
Java
int mid = left + (right - left) / 2 ;
事實(shí)上，int mid = left + (right - left) / 2 在 right 很大烈涮、 left 是負(fù)數(shù)且很小的時(shí)候， right - left 也有可能超過(guò) int 類型能表示的最大值窖剑，只不過(guò)一般情況下 left 和 right 表示的是數(shù)組索引值坚洽，left 是非負(fù)數(shù)，因此 right - left 溢出的可能性很小西土。
public class Solution {
public int searchInsert(int[] nums, int target) {
int len = nums.length;
if (len == 0) {
return 0;
}
int left = 0;
int right = len;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
}
更好的寫(xiě)法是：
Java
int mid = (left + right) >>> 1 ;
int mid=(left+right)>>>1與 int mid=(left+right)/2有什么區(qū)別
>>>是右移運(yùn)算讶舰，在計(jì)算機(jī)中是一種運(yùn)算操作，但是他的運(yùn)算結(jié)果正好能對(duì)應(yīng)一個(gè)整數(shù)的二分之一值需了，這就正好能代替數(shù)學(xué)上的除2運(yùn)算跳昼，但是比除2運(yùn)算要快。
(1)如果 left 和 right 表示的是數(shù)組的索引肋乍，就要考慮“索引是否有效” 鹅颊，即“索引是否越界” 是重要的定界依據(jù)；
左右邊界一定要包括目標(biāo)元素墓造，當(dāng) target 比數(shù)組中的最后一個(gè)數(shù)字還要大（不能等于）的時(shí)候堪伍，插入元素的位置就是數(shù)組的最后一個(gè)位置 + 1，即 (len - 1 + 1 =) len觅闽，如果忽略掉這一點(diǎn)帝雇，把右邊界定為 len - 1 ，代碼就不能通過(guò)在線測(cè)評(píng)蛉拙。
(2)中位數(shù)先寫(xiě)int mid = (left + right) >>> 1 ; 根據(jù)循環(huán)里分支的編寫(xiě)情況尸闸，再做調(diào)整理解這一點(diǎn)，首先要知道：當(dāng)數(shù)組的元素個(gè)數(shù)是偶數(shù)的時(shí)候，中位數(shù)有左中位數(shù)和右中位數(shù)之分吮廉。
當(dāng)數(shù)組的元素個(gè)數(shù)是偶數(shù)的時(shí)候：
使用 int mid = left + (right - left) / 2 ;得到左中位數(shù)的索引睹栖；
使用int mid = left + (right - left + 1) / 2 ; 得到右中位數(shù)的索引。
當(dāng)數(shù)組的元素個(gè)數(shù)是奇數(shù)的時(shí)候茧痕，以上二者都能選到最中間的那個(gè)中位數(shù)野来。
其次，
int mid = left + (right - left) / 2 ; 等價(jià)于int mid = (left + right) >>> 1踪旷；
int mid = left + (right - left + 1) / 2 ; 等價(jià)于int mid = (left + right + 1) >>> 1;
記憶方法：
(right - left) 不加 1 選左中位數(shù)曼氛，加 1 選右中位數(shù)。
public class Solution {
public int searchInsert(int[] nums, int target) {
int len = nums.length;
if (len == 0) {
return 0;
}
int left = 0;
int right = len;
while (left < right) {
int mid = left + ((right - left) >>> 1);
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
}
