Monday, August 10, 2015

Leetcode: Search in Rotated Sorted Array (4ms) analysis and solution

PROBLEM:
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.









Analysis:
Transformed binary searching (BS). 
Since it has been sorted but just rotated once, we need to make full use of the sorted feature. 
Based on the binary search, we continue to use BS but in a little different way. Anyway, we need to drop half of the vector after each search. 
See figure below for detailed implementation for how to drop half of vector after each searching. 

There are two cases in this condition, so we need to identify each case first. After identifying the two cases, in each case, we need to further identify that we need to keep the left side or right side. 
After those identification, finally we can keep one half of the vector in each searching, which is similar to the running time of BS, O(lgn). 
////////////////////////////////////////////////////////////////////////////////
//code 4ms
class Solution {
public:
       int search(vector<int>& nums, int target) {
              int n = nums.size(), mid = n / 2;
              int l = 0, r = n - 1;
              while (l <= r){
                     if (target<nums[mid]){
                           //case 1
                           if (nums[l] <= nums[mid]){
                                  if (target >= nums[l]){//left side
                                         r = mid - 1;
                                         mid = (l + r) / 2;
                                  }
                                  else{//right side
                                         l = mid + 1;
                                         mid = (l + r) / 2;
                                  }
                           }
                           //case 2
                           else{//left side
                                         r = mid - 1;
                                         mid = (l + r) / 2;
                           }
                     }
                     else if (target>nums[mid]){
                           //case 2
                           if (nums[r] >= nums[mid]){
                                  if (nums[r] >= target){//right side
                                         l = mid + 1;
                                         mid = (l + r) / 2;
                                  }
                                  else{//left side
                                         r = mid - 1;
                                         mid = (l + r) / 2;
                                  }
                           }
                           //case 1
                           else {//right side
                                  l = mid + 1;
                                  mid = (l + r) / 2;
                           }
                     }
                     else return mid;
              }
              return -1;
       }
};


No comments:

Post a Comment