題目

整數(shù)數(shù)組 nums 按升序排列，數(shù)組中的值互不相同。在傳遞給函數(shù)之前，nums 在預(yù)先未知的某個下標(biāo) k（0 <= k < nums.length）上進(jìn)行了 旋轉(zhuǎn)，使數(shù)組變?yōu)?[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下標(biāo) 從 0 開始 計數(shù)）。例如， [0,1,2,4,5,6,7] 在下標(biāo) 3 處經(jīng)旋轉(zhuǎn)后可能變?yōu)?[4,5,6,7,0,1,2] 。
給你旋轉(zhuǎn)后的數(shù)組 nums 和一個整數(shù) target ，如果 nums 中存在這個目標(biāo)值 target ，則返回它的下標(biāo)，否則返回 -1 。
你必須設(shè)計一個時間復(fù)雜度為 O(log n) 的算法解決此問題。

例：
輸入：nums = [4,5,6,7,0,1,2], target = 0
輸出：4

方法：二分查找

因為要求使用時間復(fù)雜度為 O(log n) 的算法，所以采用二分查找

• left 和 right 分別表示左右指針，left 指向數(shù)組的首部，right 指向數(shù)組的尾部
• 循環(huán)直至 left 位于 right 的右側(cè)
  • mid 表示此時中點
  • 若 mid 下標(biāo)對應(yīng)的元素值等于目標(biāo)值 target，那么找到目標(biāo)值，返回此時下標(biāo)
  • 因為此時的數(shù)組 nums 是通過一次旋轉(zhuǎn)得到的，那么從中間分開后，兩側(cè)至少有一側(cè)是升序排列的。若左邊新數(shù)組的首部元素值 nums[0] 小于尾部元素值 nums[mid]，及左邊數(shù)組是升序排列的，那么可以通過判斷目標(biāo)值 target 是否位于該區(qū)間內(nèi)，縮小查找范圍
    • 若目標(biāo)值 target 存在于 [[nums[0], nums[mid])，那么目標(biāo)值在該區(qū)間內(nèi)，縮小范圍，將右指針 right 指向中點左移一步后的位置 mid - 1
    • 若目標(biāo)值 target 不存在于 [nums[0], nums[mid])，那么目標(biāo)值在右邊新數(shù)組中，縮小范圍，將左指針 left 指向中點右移一步后的位置 mid + 1
  • 否則，右邊數(shù)組是升序排列的，那么可以通過判斷目標(biāo)值 target 是否位于該區(qū)間內(nèi)，縮小查找范圍
    • 若目標(biāo)值 target 存在于 (nums[mid], nums[len(nums)-1]]，那么目標(biāo)值在該區(qū)間內(nèi)，縮小范圍，將左指針 left 指向中點右移一步后的位置 mid + 1
    • 若目標(biāo)值 target 不存在于 (nums[mid], nums[len(nums)-1]]，那么目標(biāo)值在左邊新數(shù)組中，縮小范圍，將右指針 right 指向中點左移一步后的位置 mid - 1
• 若不存在目標(biāo)值 target，返回 -1

class Solution(object):
    def search(self, nums, target):
        left, right = 0, len(nums)-1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            if nums[0] <= nums[mid]:
                if nums[0] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if nums[mid] < target <= nums[len(nums)-1]:
                    left = mid + 1
                else:
                    right = mid - 1
        return -1

相關(guān)知識

• 二分查找：
  首先，假設(shè)表中元素是按升序排列，將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個子表，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一子表，否則進(jìn)一步查找后一子表。重復(fù)以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。
  要求線性表必須采用順序存儲結(jié)構(gòu)，而且表中元素按關(guān)鍵字有序排列。

參考

代碼相關(guān)：https://leetcode.cn/problems/search-in-rotated-sorted-array/solution/sou-suo-xuan-zhuan-pai-xu-shu-zu-by-leetcode-solut/
二分查找：https://baike.baidu.com/item/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/10628618?fr=aladdin