【題目描述】
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.
給定一個排序數(shù)組和一個目標(biāo)值，如果在數(shù)組中找到目標(biāo)值則返回索引挟憔。如果沒有俱箱，返回到它將會被按順序插入的位置澎现。你可以假設(shè)在數(shù)組中無重復(fù)元素独泞。
【題目鏈接】
www.lintcode.com/en/problem/search-insert-position/
【題目解析】
這道題目基本上就是對標(biāo)準(zhǔn)二分查找的細(xì)微修改胧卤，主要考察對于細(xì)節(jié)和邊界情況的考慮把握大莫。
由于查找的是一個特定的位置烈炭，并且要在這個位置插入Target，并且保證新的序列仍然是有序的优妙，不妨來看看給出的樣例乘综，分析一下具體的規(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ù)字都小的情況晶疼，插入到序列的開始
綜上所述酒贬，我們可以得出這樣的結(jié)論：
如果Target < nums[0]，即比所有數(shù)都小冒晰，則 Ans = 0
否則同衣，Ans = max{i | nums[i] < Target} + 1，即“最大的小于Target的數(shù)”之后壶运。
對于第一種情況耐齐，我們可以輕松判斷，而對于第二種情況蒋情，我們的問題就變成了如何尋找“最大的小于Target的數(shù)”埠况。
不妨用q(l, r)表示nums[l..r]中“最大的小于Target的數(shù)”，那么我們最終的答案就可以用q(0, size - 1) + 1來表示棵癣。
而q(l, r)的求解可以用這樣的方式來進(jìn)行計(jì)算：
不妨設(shè) m = (l + r + 1) / 2辕翰，此時：
如果 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ī)呐评铮縮小一半，所以最終我們一定會遇到一個問題q(l, r)滿足l=r务甥，此時我們就很容易知道牡辽，q(l, r)=l，則這也就是之前的所有問題的答案敞临。
【參考答案】
