題目出處：https://leetcode.com/problems/search-in-rotated-sorted-array/
如圖，給個有序位移過的Array求目標k值的index。
乍看不困難，其實就是不困難，怎麼寫怎麼提交怎麼過。
就算題目是亂序的用同套代碼也能解。根本秒殺，下一題。
#python3 代碼：
class Solution:
def search(self, nums: List[int], target: int) -> int:
//取得長度
length = len(nums)
//設立指標 i，下去檢查每個元素。
for i in range(length):
if nums[i] == target:
//回傳下標結束函數。
return i
//若跑完所有元素都沒有發現target，依照題意返回 -1
return -1換其他語言寫也是一分鐘內生出來
#golang 代碼：
func search(nums []int, target int) int {
for index, value := range nums{
if value == target{
return index
}
}
return -1
}但可惜事情不會這那麼簡單，嚴格來說上面的代碼都是零分。
至於為什麼呢。可以聽我娓娓道來。
其實在仔細看題目會發現他有一句話：
You must write an algorithm with O(log n) runtime complexity.
翻譯成人話就是要求必須寫成O(log n)時空間複雜度。也就是限定你要用二分法解。
O(n)與O(n平方)像這樣的關鍵字都是度量你的代碼需要多少資源來解決問題。
談的是時間複雜度或空間複雜度的問題，這類東西我也沒做很多深入研究。
舉例來說如果你要遍歷一次就是O(n)，
如果你遍歷裡面還要遍歷就是O(n平方)也就是for用兩次之類的。
如果理解有誤也歡迎指正。
通常不會想那麼多，能解決問題就好，以前當學生時期在考試的時候也是看到圖就直接算了。
但是如果今天上機考題目有指定，但你不遵守規則，就算提交給過了，在面試官心中還是默默地扣分。
自己還不知道發生什麼事，以為自己答的上來已經沒問題了，殊不知一開始的方向就錯了。
我個人是這樣覺得有時候面試吃的就是你跟面試官的緣分。
也有可能面試官覺得你的代碼邏輯他不習慣或者是Coding Style不符合公司規範，總之原因可能有很多。
有時候面試未錄取。也不用太氣餒。
不管在哪個階段就盡自己所能就好了。
二分法解：
在兩個區塊上查找目標，題目把Array位移了但還是可以分為大區跟小區，也就是數字大的區域跟小的區域。在數組中隨機找個點插入指針。插在大區的話可以再分兩種情況討論，小區的話也是一樣。概括就是目標在指針的右邊還是左邊。左邊的話就刪除右邊。右邊的話就刪除左邊。在有排序的數組下使用這種方式可以大幅優化查找效率。
#python3 代碼：
class Solution:
def search(self, nums: List[int], target: int) -> int:
# 取得左右下標
left, right = 0, len(nums)-1
# 當左指針指到右邊的左邊一格就結束while
while left+1 < right:
# 二分法須先取中線，以中線進行二分下去討論所有狀況
mid_index = (left + right)//2
# 如果中線是落在大區域
if nums[mid_index] > nums[right]:
# 如果目標在大區的左邊。也就是比中線小又比左邊大。
if nums[left] <= target <= nums[mid_index]:
# 就直接把右指針移動到中線
right = mid_index
else:
# 反之沒在左邊，就把左邊整個砍掉
left = mid_index
# 如果中線是落在小區域
else:
# 如果目標在小區的右邊。也就是比中線大又比右邊小。
if nums[mid_index] <= target <= nums[right]:
left = mid_index
else:
# 反之沒在右邊，就把右邊整個砍掉
right = mid_index
# 到最後就會收束成兩個下標，查找兩次。
if nums[right] == target:
return right
if nums[left] == target:
return left
# 若都查找不到一題意返回 -1
return -1太苦了！如果有其他想法的話歡迎交流喔。