image.png

0. 鏈接

1. 需求

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm's runtime complexity must be in the order of O(log n).

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

2. 思路1: 先用二分法找到數(shù)組旋轉(zhuǎn)點, 再從兩部分數(shù)組中分別用二分法尋找

2.1 算法步驟

例如從nums=[4, 5, 6, 7, 0, 1, 2]中查找target=0
過程如下:

1) 先用二分法尋找到旋轉(zhuǎn)點7對應下標split_index=3
2) 如果target < nums[0]
        則從nums[0: split_index + 1]中二分查找target所處下標
   否則
        則從nums[split_index + 1:-1]中二分查找target所處下標result_index
        如果結(jié)果不為-1，則返回split_index + 1 + result_index

2.2 代碼

# coding:utf8


class Solution:
    def binary_search(self, nums, target):
        left = 0
        right = len(nums) - 1

        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            elif target > nums[mid]:
                left = mid + 1
            elif target < nums[mid]:
                right = mid - 1

        return -1

    def search_pivot(self, nums):
        left = 0
        right = len(nums) - 1

        while left < right:
            mid = (left + right) // 2
            if nums[mid] > nums[left] and nums[mid] > nums[right]:
                left = mid
            elif nums[mid] < nums[left] and nums[mid] < nums[right]:
                right = mid
            else:
                break

        return left

    def search(self, nums, target: int) -> int:
        if len(nums) == 0:
            return -1

        if nums[0] < nums[-1]:
            return self.binary_search(nums, target)

        pivot_index_left = self.search_pivot(nums)
        if pivot_index_left == -1:
            return -1

        if target < nums[0]:
            target_idx = self.binary_search(nums[pivot_index_left + 1:], target)
            return pivot_index_left + 1 + target_idx if target_idx != -1 else -1
        else:
            return self.binary_search(nums[:pivot_index_left + 1], target)


solution = Solution()
print(solution.search([4, 5, 6, 7, 0, 1, 2], 0))  # 4
print(solution.search([], 1)) # -1
print(solution.search([1], 1)) # 0
print(solution.search([1, 3], 1)) # 0
print(solution.search([1, 3, 0], 0)) # 2

2.3 結(jié)果

image.png

3. 思路2: 只用一次二分查找解決問題

3.1 算法步驟

1. 已知數(shù)組含有兩個分別有序的子數(shù)組, 
2. 定義left=0, right=len(array) - 1,
 while left <= right do
    計算mid = (left + right) // 2,
     如果 nums[mid] == target 則
        返回mid
     否則
        判斷mid處元素和target是否處于同一個子數(shù)組
            1) 如果array[mid] >= nums[0] > target, 即mid處于左子數(shù)組, 而target處于右子數(shù)組, 此時需要
                left = mid + 1, 試圖接近target所處的位置
            2) 如果array[mid] < nums[0] <= target, 即mid處于右子數(shù)組, 而target處于左子數(shù)組, 此時需要
                right = mid - 1, 試圖接近target所處的位置
            3) 1和2都不滿足, 則說明mid和target處于同一個子數(shù)組,此時可以走正常二分查找的步驟, 即:
                if target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
        
 return -1

3.2 代碼

class SolutionSimple:
    def search(self, nums, target):
        if len(nums) == 0:
            return -1

        left = 0
        right = len(nums) - 1

        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid

            if nums[mid] >= nums[0] > target:
                left = mid + 1
            elif nums[mid] < nums[0] <= target:
                right = mid - 1
            else:
                if target > nums[mid]:
                    left = mid + 1
                else:
                    right = mid - 1

        return -1


solution = SolutionSimple()
print(solution.search([4, 5, 6, 7, 0, 1, 2], 0))    # 4
print(solution.search([], 1))         # -1
print(solution.search([1], 1))        # 0
print(solution.search([1, 3], 1))     # 0 
print(solution.search([1, 3, 0], 0))  # 2
print(solution.search([4, 5, 6, 7, 0, 1, 2], 3))    # -1

3.3 結(jié)果

image.png