[LeetCode] Search in Rotated Sorted Array I (33) && II (81) 解题思路

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.

You may assume no duplicate exists in the array.

问题：给定一个已排序的数组，该数组以某一个元素作为支点做了旋转，在改旋转后数组中搜索值。

已排序数组的搜索，自然会想到二分搜索。将旋转到后面的部分用负数表示下标，便可以正常使用二分搜索。

需要注意的是对比元素值和目标值时，记得将下标转会正数 ( i + len ) % len 。

=================================

81. Search in Rotated Sorted Array II

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

问题：若 Search in Rotated Sorted Array 中的数组存在重复元素，如何解决原问题？

重复元素对于上面算法唯一一个影响，就是算法实现时候，判断是否有旋转需要更严谨一点。

第一题代码：

 1     int search(vector<int>& nums, int target) {
 2         
 3         int len = (int)nums.size();
 4 
 5         if (len == 0){
 6             return -1;
 7         }
 8         
 9         if ( len == 1 ){
10             return (nums[0] == target) ? 0 : -1;
11         }
12         
13         int realL;
14         int realR;
15         if (nums[0] > nums[len-1]) {
16             for ( int i = 0 ; i < len ; i++){
17                 if (nums[i] > nums[i+1]){
18                     realR = i;
19                     break;
20                 }
21             }
22             
23             realL = realR - len + 1;
24         }else{
25             realL = 0;
26             realR = len - 1;
27         }
28                 
29         while( realL < realR ){
30             
31             if (realL + 1 == realR){
32                 int idxL = ( realL + len ) % len;
33                 int idxR = ( realR + len ) % len;
34                 
35                 if (nums[idxL] == target){
36                     return idxL;
37                 }
38                 
39                 if (nums[idxR] == target){
40                     return idxR;
41                 }
42                 
43                 return -1;
44             }
45             
46             int mid = ( realL + realR ) / 2;
47             int idx = ( mid + len ) % len;
48             
49             if (nums[idx] == target){
50                 return idx;
51             }
52             
53             if (nums[idx] < target){
54                 realL = mid;
55             }else{
56                 realR = mid;
57             }
58         }
59         
60         // Actually, program will never step to here. It will return value previously.
61         return -1;
62     }

View Code

第二题代码：

    bool search(vector<int>& nums, int target) {
        
        int len = (int)nums.size();

        if (len == 0){
            return false;
        }
        
        if ( len == 1 ){
            return (nums[0] == target) ? 1 : 0;
        }
        
        int realL;
        int realR;
        
        int ii = 0;
        while (ii < len - 1) {
            if (nums[ii] <= nums[ii + 1]) {
                ii++;
                continue;
            }else{
                break;
            }
        }
        
        if (ii == len - 1 ) {
            realL = 0;
            realR = len - 1;
        }else{
            realR = ii;
            realL = realR - len + 1;
        }
        
        while( realL < realR ){
            
            if (realL + 1 == realR){
                int idxL = ( realL + len ) % len;
                int idxR = ( realR + len ) % len;
                
                if (nums[idxL] == target){
                    return true;
                }
                
                if (nums[idxR] == target){
                    return true;
                }
                return false;
            }
            
            int mid = ( realL + realR ) / 2;
            int idx = ( mid + len ) % len;
            
            if (nums[idx] == target){
                return true;
            }
            
            if (nums[idx] < target){
                realL = mid;
            }else{
                realR = mid;
            }
        }
        
        // Actually, program will never step to here. It will return value previously.
        return -1;
    }

View Code