題目：給定一個(gè)排序數(shù)組和一個(gè)目標(biāo)值拗军，在數(shù)組中找到目標(biāo)值殊轴，并返回其索引钦奋。如果目標(biāo)值不存在于數(shù)組中座云，返回它將會(huì)被按順序插入的位置疙赠。
你可以假設(shè)數(shù)組中無(wú)重復(fù)元素。
個(gè)人解法（java）：
class Solution {
public int searchInsert(int[] nums, int target) {
for(int i = 0; i < nums.length; i++) {
if(target <= nums[i]) {
return i;
}
}
return nums.length;
}
}
較優(yōu)解法（來(lái)自leetcode官網(wǎng)）：
降低時(shí)間復(fù)雜度
標(biāo)簽：二分查找
如果該題目暴力解決的話需要O(n) 的時(shí)間復(fù)雜度朦拖，但是如果二分的話則可以降低到 O(logn) 的時(shí)間復(fù)雜度
整體思路和普通的二分查找?guī)缀鯖](méi)有區(qū)別棺聊，先設(shè)定左側(cè)下標(biāo) left 和右側(cè)下標(biāo) right，再計(jì)算中間下標(biāo) mid
每次根據(jù) nums[mid] 和 target 之間的大小進(jìn)行判斷贞谓，相等則直接返回下標(biāo)限佩，nums[mid] < target 則 left 右移，nums[mid] > target 則 right 左移
查找結(jié)束如果沒(méi)有相等值則返回 left裸弦，該值為插入位置
時(shí)間復(fù)雜度：O(logn)
二分查找的思路不難理解祟同，但是邊界條件容易出錯(cuò)，比如 循環(huán)結(jié)束條件中 left 和 right 的關(guān)系理疙，更新 left 和 right 位置時(shí)要不要加 1 減 1
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while(left <= right) {
int mid = (left + right) / 2;
if(nums[mid] == target) {
return mid;
} else if(nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
}
