首页 > 代码库 > LeetCode 33. Search in Rotated Sorted Array(在旋转有序序列中搜索)

LeetCode 33. Search in Rotated Sorted Array(在旋转有序序列中搜索)

Suppose an array sorted in ascending order 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.

 

 


题目标签:Array
  题目中给了我们一个旋转有序序列,让我们找到target的index。 其实利用最基本的一个一个找过来都可以通过- -, 题目应该说的更明确一点。让我们利用binary search来搜索。
  以往我们利用binary search 来找的话,都是在排序好了的array里面。但是这一题,array不一定是排序好的。大部分情况都是一个array里,分2边,各自都是排序好的,但是中间有一个断点。我们来看原题中的例子:
 
  0  1  2  4  5  6  7  最原始的时候是有序排列的, 现在开始向左rotate
  1  2  4  5  6  7  0  从这时候开始,一边是有序的,另外一边也是有序的,中间有断点。
       2  4  5  6  7  0  1
  4  5  6  7  0  1  2
  5  6  7  0  1  2  4
  6  7  0  1  2  4  5
  7  0  1  2  4  5  6
  0  1  2  4  5  6  7  这里就回到了最初的情况
 
  来分析一下,一旦开始rotate, 就变成分开的两个有序序列,中间有个断点在移动。因为这个断点一直在移动,所以不好根据这个变量来判断。那么我们来找一个不变量来判断。
  我们看每次中间红色的点,当这个中间点比最左边蓝色的点大的时候,说明 左边的这半(包括中间点)一定是有序序列。右边的话,不确定。
  当这个中间的点没有比左边点大的时候,那么说明右边的有序序列已经移动过来了,并且占据了中间点,那么右边的一半(包括中间点)一定是有序序列。
 
  在了解这个规律后,就可以利用binary search来搜索了,binary search就是要判断,target 在哪一边,然后继续走到那一边里继续搜索。这里我们要通过那一半肯定是有序序列来帮助查找。首先判断中间点是不是target,不是的话就判断target是不是在有序序列里,通过有序序列里的两边来判断。是的话就继续跑到有序的那一边去继续搜索。如果不是在有序序列里,那么就跑到另外一边里面去继续搜索。
 
 

Java Solution:

Runtime beats 70.31% 

完成日期:07/14/2017

关键词:Array

关键点:利用Binary Search 结合 rotated sorted array 中必然有一半是有序序列 来搜索

 

 1 public class Solution 
 2 {
 3     public int search(int[] nums, int target) 
 4     {
 5        if(nums == null || nums.length == 0)
 6             return -1;
 7         
 8         int left = 0;
 9         int right = nums.length - 1;
10         
11         while(left <= right)
12         {
13             int mid = left + (right - left) / 2;
14             
15             if(nums[mid] == target) // if the middle one is target, return mid index
16                 return mid;
17             else if(nums[mid] >= nums[left]) // meaning left half is ascending order 
18             {
19                 if(target >= nums[left] && target < nums[mid]) // if target is in left half
20                     right = mid - 1; // move to left half to search
21                 else // target is in right half
22                     left = mid + 1; // move to right half to search
23             }
24             else // meaning right half is ascending order
25             {
26                 if(target > nums[mid] && target <= nums[right]) // if target is in right half
27                     left = mid + 1;
28                 else // target is in left half
29                     right = mid - 1;
30                     
31             }
32             
33         }
34         
35         
36         return -1;
37     }
38 }

参考资料:

http://www.cnblogs.com/grandyang/p/4325648.html

 

LeetCode 算法题目列表 - LeetCode Algorithms Questions List

   
 

LeetCode 33. Search in Rotated Sorted Array(在旋转有序序列中搜索)