[algorithm] Binary search變形

基本的binary search

http://oj.leetcode.com/problems/search-in-rotated-sorted-array/
排序過的array但是往左circular shift過，沒有重複。mid切開後，左右兩邊至少會有一邊是正常排序過的順序，判斷哪邊是，然後看target有沒有在正常排序過的那塊裡面，沒有的話就在另外一塊。
雖然元素不會重複，但是判斷A[low]和A[mid]的時候要用<=，因為mid可能會等於low。

同上，有重複
http://oj.leetcode.com/problems/search-in-rotated-sorted-array-ii/

array呈現鋸齒狀，先遞增再遞減，沒有重複。先用binary search找出peak，找到後兩邊各用一般的binary search即可。 給一個array，每個數字都出現兩次，只有一個出現一次，找出只出現一次的那個。用XOR是O(N)，假如已經排序過了，可以怎麼最佳化。（每次去找中間點是不是unique，不是的話根據左右兩邊的個數判斷unique會出現在哪邊） 如果現在有一個API可以輸入股票名稱還有一段日期區間，他會回應在該日期區間內該股票第一次有交易資訊的日期，如果還沒有交易過的話回傳null。每次運算都是O(N) (從start date掃到end date，有交易的時候就回傳），現在你要寫一個函式把這個原始的函式包起來然後加速，你要怎麼做。
很神奇的這個也是binary search。有了start date和end date，算mid date，呼叫原始的API但是start date和end date都設成mid date，所以如果在mid date的時候該股票已經上市，原來的end date = mid date，如果還沒上市，start date = mid date。