Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Search in Rotated Sorted Array

Leetcode algorithms 第 33 题:Search in Rotated Sorted Array。

题目

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.

解答

这是一个翻转过一次的升序数组,由于原本是升序的,翻转过一次后,变成两段升序的子数组,而且左半段数组的数值都比右半段数组的数值大。如下图所示,左边数组翻转后变成右边两段子数组:

              /    |          /
            /      |        /
          /        |      /
        /          |    /
      /            |                    /
    /              |                  /
  /                |                /
/                  |              /

在这两段升序数组中求首尾的中间位置时,可能出现在左半段,也可能出现在右半段,以下分情况讨论:

  • mid在左半段:如果A[st] <= target < A[mid],那么target在mid的左边;否则target在mid的右边
  • mid在右半段:如果A[mid] < target <= A[ed],那么target在mid的右边,否则target在mid的左边

现在根据这个分类标准进行二分搜索,具体代码如下:

class Solution {
public:
    int search(int A[], int n, int target) {
        if (n <= 0) return false;

        int st = 0, ed = n - 1;
        while (st <= ed)
        {
            int mid = st + ((ed - st) >> 1);
            if (target == A[mid]) return mid;//找到
           
            if (A[mid] >= A[st]) //中间点在左半段
            {
                if (target >= A[st] && target < A[mid]) ed = mid - 1; //target在mid左边
                else st = mid + 1;
            }
            else                //中间点在右半段
            {
                if (target <= A[ed] && target > A[mid]) st = mid + 1; //target在mid右边
                else ed = mid - 1;
            }
        }
        return -1;
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论