九章算法 | Google面试题：搜索旋转排序数组

描述

假设有一个排序的按未知的旋转轴旋转的数组(比如，0 1 2 4 5 6 7 可能成为4 5 6 7 0 1 2)。给定一个目标值进行搜索，如果在数组中找到目标值返回数组中的索引位置，否则返回-1。你可以假设数组中不存在重复的元素。

在线评测地址：九章算法

样例1

输入: [4, 5, 1, 2, 3] and target=1, 
输出: 2.

样例2

输入: [4, 5, 1, 2, 3] and target=0, 
输出: -1.

算法：二分

用两次二分的方法。

第一次二分：找到最小数的位置，参考 find minimum number in rotated sorted array

第二次二分：确定 target 在左侧区间还是右侧，用一个普通的二分法即可找到。

class Solution:
    """
    @param A: an integer rotated sorted array
    @param target: an integer to be searched
    @return: an integer
    """
    def search(self, A, target):
        if not A:
            return -1

        index = self.find_min_index(A)
        if A[index] <= target <= A[-1]:
            return self.binary_search(A, index, len(A) - 1, target)
        return self.binary_search(A, 0, index - 1, target)

    def find_min_index(self, A):
        start, end = 0, len(A) - 1
        while start + 1 < end:
            mid = (start + end) // 2
            if A[mid] < A[end]:
                end = mid
            else:
                start = mid

        if A[start] < A[end]:
            return start
        return end

    def binary_search(self, A, start, end, target):
        while start + 1 < end:
            mid = (start + end) // 2
            if A[mid] < target:
                start = mid
            else:
                end = mid
        if A[start] == target:
            return start
        if A[end] == target:
            return end
        return -1

更多题解参考：九章算法