leetcode做题记录 —— search-in-rotated-sorted-array

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.

search-in-rotated-sorted-array

给定一个有序但是被旋转过的数组，旋转的长度未知，比如 
[0, 1, 2, 4, 5, 6, 7] 旋转后为 [4, 5, 6, 7, 0, 1, 2] 
给定一个值，要求在这个数组中查找，如果找到返回在数组中的位置，否则返回-1。

解法

由于是有序数组，用二分就可以，但是经过旋转，所以要做一些判断。 
需要对分出的两边进行判断否为正常排序的一边 
如果右边为正常排序的半边，判断目标是否在右半边，然后更新边界 
如果左边为正常排序的半边，判断目标是否在左半边，然后更新边界

1.//Javascript
2.var search = function(nums, target) {
3.    let left = 0;  
4.    let right = nums.length -1;  
5.    while( left <= right )
6.    {
7.        let mid = (left + right) >> 1;  
8.        if( target === nums[mid] )  
9.        {    
10.            return mid;  
11.        }
12.        if( nums[mid] < nums[right] )  
13.        {  
14.            //右半边为正常排序，
15.            //所以只需要判断目标是否在右半边，即可确定下一次查询的范围
16.            if( target > nums[mid] && target <= nums[right] )  
17.            {
18.                left = mid + 1;  
19.            }
20.            else  
21.            {
22.                right = mid - 1;  
23.            }
24.        }  
25.        else  
26.        {
27.            //右半边不为正常排序，则表明左半边为正常排序，
28.            //所以只需要判断目标是否在左半边，即可确定下一次查询的范围
29.            if( target >= nums[left] && target < nums[mid] )  
30.            {
31.                right = mid - 1;
32.            }    
33.            else  
34.            {    
35.                left = mid + 1;
36.            }
37.        }  
38.    } 
39.    return -1;  
40.};

End