【題目描述】
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.You may assume NO duplicates in the array.
給定一個(gè)排序數(shù)組和一個(gè)目標(biāo)值，如果在數(shù)組中找到目標(biāo)值則返回索引。如果沒(méi)有，返回到它將會(huì)被按順序插入的位置。你可以假設(shè)在數(shù)組中無(wú)重復(fù)元素。
【題目鏈接】
www.lintcode.com/en/problem/search-insert-position/
【題目解析】
這道題目基本上就是對(duì)標(biāo)準(zhǔn)二分查找的細(xì)微修改，主要考察對(duì)于細(xì)節(jié)和邊界情況的考慮把握。
由于查找的是一個(gè)特定的位置，并且要在這個(gè)位置插入Target，并且保證新的序列仍然是有序的，不妨來(lái)看看給出的樣例，分析一下具體的規(guī)則：
[1,3,5,6], 2 → 1，這是最為普通的情況，由于1<2<3，直接插入在1和3的中間即可。
[1,3,5,6], 5 → 2，這是已經(jīng)存在了相同數(shù)字的情況，在這種情況下，應(yīng)當(dāng)插入到相同的數(shù)字之前。
[1,3,5,6], 7 → 4，這是比所有數(shù)字都大的情況，插入到序列的最后
[1,3,5,6], 0 → 0，這是比所有數(shù)字都小的情況，插入到序列的開(kāi)始
綜上所述，我們可以得出這樣的結(jié)論：
如果Target < nums[0]，即比所有數(shù)都小，則 Ans = 0
否則，Ans = max{i | nums[i] < Target} + 1，即“最大的小于Target的數(shù)”之后。
對(duì)于第一種情況，我們可以輕松判斷，而對(duì)于第二種情況，我們的問(wèn)題就變成了如何尋找“最大的小于Target的數(shù)”。
不妨用q(l, r)表示nums[l..r]中“最大的小于Target的數(shù)”，那么我們最終的答案就可以用q(0, size - 1) + 1來(lái)表示。
而q(l, r)的求解可以用這樣的方式來(lái)進(jìn)行計(jì)算：
不妨設(shè) m = (l + r + 1) / 2，此時(shí)：
如果 nums[m] < target，則“最大的小于Target的數(shù)”至少是nums[m]，由于nums[l..m-1]均小于nums[m]，所以可以知道l..m-1都不可能是答案（不可能是最大的），即q(l, r) = q(m, r)
如果 nums[m] >= target，由于nums[r]>nums[r-1]>...>..>nums[m]>=target，可知m..r均不可能為答案（不小于Target），即q(l, r) = q(l, m - 1)
在這樣的處理過(guò)程中，我們每次可以將問(wèn)題的規(guī)?？s小一半，所以最終我們一定會(huì)遇到一個(gè)問(wèn)題q(l, r)滿足l=r，此時(shí)我們就很容易知道，q(l, r)=l，則這也就是之前的所有問(wèn)題的答案。
【參考答案】
