LeetCode33 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.

You may assume no duplicate exists in the array. （Hard）

分析：

跟旋转排序数组（rotated sorted array）有关的的问题，一般可以考虑二分的思路。

之前的总结见：

http://www.cnblogs.com/wangxiaobao/p/4915853.html

本题就是要搞清楚什么时候start = mid 什么时候end = mid即可，画图是想明白的最好的方法。

比如下面这幅很丑的图就能说明意思，左括号代表start = mid，右括号代表 end = mid，星号是target的位置。

可以看出，start = mid

在 target > nums[0] （左图）的时候有一种情况即 nums[0] < nums[mid] < target;

在target < nums[0]（右图）的时候有两种情况，即nums[mid] > nums[0] || nums[mid] < target;

其他情况就时end = mid了。

nums[0] ==target单独判断一下，这样后续判断条件清晰一些。

代码：

 class Solution {

 public:

     int search(vector<int>& nums, int target) {

         int start = , end = nums.size() - ;

         if (nums[] == target) {

             return ;

         }

         while (start +  < end) {

             int mid = start + (end - start) / ;

             if (nums[mid] == target) {

                 return mid;

             }

             else if ( (target > nums[] && (nums[mid] < target && nums[mid] > nums[] ))

                     || (target < nums[] && (nums[mid] < target || nums[mid] > nums[])) ) {

                 start = mid;

             }

             else {

                 end = mid;

             }

         }

         if (nums[start] == target) {

             return start;

         }

         if (nums[end] == target) {

             return end;

         }

         return -;

     }

 };

巴特西

LeetCode33 Search in Rotated Sorted Array

最新文章

热门文章