[leetcode][python]33. Search in Rotated Sorted Array

這題要求O(log n) 的時間複雜度，因此我使用binary search的方式
但由於這個排序的數列的起始點並不是在第一個元素，而是可能在任何地方，所以需要做額外判斷

做法如下:

• 使用遞迴的方式，每次將檢查的數列切一半
• 判斷要尋找的數字在哪一邊
• 當數列開頭與結尾的idx 相同時，代表沒資料，不做事
• 當數列開頭與結尾的idx 相差1時，代表只有一筆資料，可用來判斷是否為要找的target
• 在其他狀況下，將數列切一半，判斷target在哪邊後，即可遞迴從那一邊繼續尋找
• 找中間index(left + (right-left)/2)
• 若最中間數字大於最左邊
• 轉折點在右邊
• 判斷target是否在左邊與中間之間
• yes: 左半邊繼續找
• no: 右半邊繼續找
• 若中間數字小於最右邊
• 轉折點在左邊
• yes: 右半邊繼續找
• no: 左半邊繼續找

source code:
https://github.com/cy-arduino/leetcode/blob/master/33.%20Search%20in%20Rotated%20Sorted%20Array.py