LeetCode 33. Search in Rotated Sorted Array 位移過的sorted array
我們把數列分成兩半，就是紅字標起來(位移的)一半跟另外一半。
這題分成兩種狀況
情況1 要找的數字跟目前mid同一半
情況2 要找的數字跟mid不同半
如果是情況1. 其實就跟平常的binary search沒兩樣
如果是情況2. 就比較特別，其實我們就是只要往target的那一個半邊(例如紅色那塊)去就好了。
綠色是要找的數字 黑色箭頭是mid
情況1 我先說一下會是怎樣 要找的數字跟 mid屬於同一邊
另外一個在紅色那半邊的
所以這時候執行正常的binary search
情況二 :其實就可想像是第一張圖 綠色箭頭在紅色那邊
第二張圖綠色箭頭在黑色那邊
這時候我們希望它無限的往綠色箭頭那邊靠。
這時候我們拿target(綠色箭頭的值) 去跟num[0](value = 7) 比較
在情況2如何靠近
以第一張圖來說因為綠色箭頭(5)是屬於黑色的array那部分，所以她跟開頭比一一比較小 所以這時候我們希望往左邊靠 就把 比較的數字設為 無限小
反之當他如下圖 他比 num[0]大 那他就設成無限大讓他往左邊靠。
主要觀念來自這邊