給定一個(gè)排序數(shù)組和一個(gè)目標(biāo)值卜录，如果在數(shù)組中找到目標(biāo)值則返回索引戈擒。如果沒(méi)有眶明，返回到它將會(huì)被按順序插入的位置艰毒。
你可以假設(shè)在數(shù)組中無(wú)重復(fù)元素。
樣例
[1,3,5,6]搜囱，5 → 2
[1,3,5,6]丑瞧，2 → 1
[1,3,5,6]， 7 → 4
[1,3,5,6]蜀肘，0 → 0
二分查找__細(xì)節(jié)
二分查找绊汹，找到了最好，找不到的話看情況插在哪里扮宠。
二分查找的while循環(huán)里的條件一定要寫對(duì)西乖，應(yīng)該是beg<=end，等于號(hào)一定不要忘記了坛增。
當(dāng)遍歷到beg和end相鄰時(shí)：這時(shí)候計(jì)算出來(lái)的mid=beg获雕。
如果是<，則下一次就直接跳出循環(huán)了收捣。循環(huán)終止時(shí)届案，beg可能大于end也可能等于end。這樣實(shí)際上是有一個(gè)值是沒(méi)有遍歷到的（就是當(dāng)前的這個(gè)end）罢艾。
如果是<=楣颠，那么可能出現(xiàn)beg=end的情況尽纽，這種情況就是mid<target時(shí)。這個(gè)時(shí)候再進(jìn)行一次循環(huán)童漩，最后跳出循環(huán)肯定是beg=end+1弄贿。所以還是有細(xì)微的差別。
為了達(dá)到這種統(tǒng)一的循環(huán)終止?fàn)顟B(tài)矫膨，選擇<=是合理的挎春，終止?fàn)顟B(tài)肯定是beg=end+1，而且mid最終的位置豆拨，就是最后一次beg的位置直奋。
這個(gè)位置的值如果大于target，那么應(yīng)該插入到這個(gè)位置前面施禾，如果小于的話脚线，應(yīng)該插入到后面。
int searchInsert(vector<int> &A, int target) {
if(A.empty()) //沒(méi)有元素的特殊情況
return 0;
auto beg=A.begin();
auto end=A.end()-1;
vector<int>::iterator mid;
while(beg<=end)
{
mid=beg+(end-beg)/2;
if(*mid==target)
return mid-A.begin();
else if(*mid<target)
{
beg=mid+1;
}
else
end=mid-1;
}
if(*mid<target)
return mid-A.begin()+1;
if(*mid>target)
return mid-A.begin();
// write your code here
}
