LeetCode: Search in Rotated Sorted Array

题目

https://oj.leetcode.com/problems/search-in-rotated-sorted-array/

分析

还是运用二分的思想, 每次循环判断target在中点的左侧还是右侧,每次砍掉一半的查找范围, 直到得到最终结果。

在这个过程中用到的一个重要规律是: 

一个数字序列经过rotate之后, 以中间那个数字为边界, 一定一边是有序序列, 一边是 rotated有序序列(证明略)。

如何判断哪边是有序的呢? 如果中点大于左边界, 则左侧是有序序列, 否则右侧是有序序列。

分别用 l代表左边界, r代表右边界, m代表中间那个数,

如果A[m] == target, 则直接返回m即可。

如果A[m] >= A[l] ,说明左侧是有序序列

       如果target在左侧有序序列范围内, 则把 左边界l 设为 m+1

       否则target在右侧序列中, 则把 右边界r 设为 m-1

否则, 右侧是有序序列

       如果target在右侧有序序列范围内, 则把 左边界l 设为 m+1

       否则target在左侧有序序列范围内, 则把 右边界r 设为 m-1

 

P.S. 标准二分查找代码可以查看这里

代码

class Solution
{
public:
    int search(int A[], int n, int target)
    {
        if (n <= 0)
            return -1;
        int l = 0;
        int r = n - 1;
        int m;

        while (l <= r)
        {
            m = (l + r) / 2;
            if (A[m] == target)
                return m;
            else if (A[l] < A[m])
            {
                if (A[l] <= target && target <= A[m-1])
                    r = m - 1;
                else
                    l = m + 1;
            }
            else
            {
                if (A[m+1] <= target && target <= A[r])
                    l = m + 1;
                else
                    r = m - 1;
            }
        }
        return -1;
    }
};

参考

http://blog.csdn.net/linhuanmars/article/details/20525681

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39860279