LintCode刷题62：Search in Rotated Sorted Array

这篇文章讲解的是LintCode第62题：Search in Rotated Sorted Array

题目描述链接

Description
Suppose a sorted array 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.

Have you met this question in a real interview?  
Example
Example 1:

Input: [4, 5, 1, 2, 3] and target=1, 
Output: 2.
Example 2:

Input: [4, 5, 1, 2, 3] and target=0, 
Output: -1.

大意是在一个旋转的有序数组中寻找一个target，如果存在则返回其索引值，不存在则返回-1.

这道题目可以用二分查找来完成。
首先脑海中就将这个旋转后的递增数组想象成为一个双曲线。
1.初始化start、end两个索引值分别为0和数组长度-1 。
2.计算mid索引值。判断：

• 假如mid处的值等于target，则返回mid
• 如果A[start]大于等于A[mid]，则说明mid处于输入数组的递增的前半部分。因此判断前半部分的情况：如果A[start]小于等于target并且target小于等于A[mid],则令end = mid,再来循环计算。
• 如果A[start]小于A[mid]，则说明mid处于输入数组的递增的后半部分。即下图的绿色部分。因此判断后半部分的情况：如果A[mid]小于等于target并且target小于等于A[end],则令end = mid,再来循环计算。
  
  python代码如下：

class Solution:
    """
    @param A: an integer rotated sorted array
    @param target: an integer to be searched
    @return: an integer
    """
    def search(self, A, target):
        # write your code here
        if A == None or len(A) == 0:
            return -1
        start, end = 0, len(A) - 1
        while start + 1 < end:
            mid = start + (end - start) // 2
            if A[mid] == target:
                return mid
            if A[start] < A[mid]:
                if A[start] <= target and target <= A[mid]:
                    end = mid
                else:
                    start = mid
            else:
                if A[mid] <= target and target <= A[end]:
                    start = mid
                else:
                    end = mid
        if A[start] == target:
            return start
        if A[end] == target:
            return end
        return -1

其中注意几个点：

1. while的判断条件是start + 1 < end，这样避免死循环和后面出现不必要的判断；
2. mid = start + (end - start) // 2能避免值溢出；
3. A在和target比较大小时加上=。