O(logn) solutions for both Search in Rotated Sorted Array I and II


  • -1
    H

    The idea is simple: first use binary search to find out the minimal element in array nums, as the minimal element divides nums into two sorted arrays, then we still use binary search to locate the target.

    Search in Rotated Sorted Array I

    class Solution {
    public:
        int orderedSearch(vector<int>& nums, int target, int left, int right) {
            while(left < right) {
                if(nums[left] > target || nums[right] < target) return -1;
                int mid = left + (right - left) / 2;
                if(nums[mid] == target) return mid;
                else if(nums[mid] > target) right = mid;
                else left = mid + 1;
            }
            return nums[left] == target ? left : -1;
        }
        
        int search(vector<int>& nums, int target) {
            int n = nums.size();
            int left = 0, right = n - 1;
            while(left < right) {
                int mid = left + (right - left) / 2;
                if(nums[mid] == target) return mid;
                if(nums[mid] > nums[right]) left = mid + 1;
                else if(nums[mid] < nums[right]) right = mid;
            }
            // nums[left] is the minimum element in array nums
            int res1 = orderedSearch(nums, target, 0, left-1);
            int res2 = orderedSearch(nums, target, left, n-1);
            return res1 != -1 ? res1 : res2 != -1 ? res2 : -1;
        }
    };
    

    Search in Rotated Sorted Array II

    class Solution {
    public:
        int orderedSearch(vector<int>& nums, int target, int left, int right) {
            while(left < right) {
                if(nums[left] > target || nums[right] < target) return false;
                int mid = left + (right - left) / 2;
                if(nums[mid] == target) return true;
                else if(nums[mid] > target) right = mid;
                else left = mid + 1;
            }
            return nums[left] == target;
        }
    
        bool search(vector<int>& nums, int target) {
            int n = nums.size();
            int left = 0, right = n-1;
            while(left < right) {
                int mid = left + (right - left) / 2;
                if(nums[mid] == target) return true;
                if(nums[mid] == nums[right]) { // delete the duplicate element
                    nums.erase(nums.begin()+right);
                    right --;
                }
                else if(nums[mid] > nums[right]) left = mid + 1;
                else right = mid;
            }
            // nums[left] is the minimum element in array nums
            n = nums.size();
            return orderedSearch(nums, target, 0, left-1) || orderedSearch(nums, target, left, n-1);
        }
    };
    

  • 0

    It's not O(logN) because delete duplicate element may take O(n) time.

    Try this test case:

    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
    2
    Deleting duplicate element make the algorithm not O(logN).

    Binary Search is a good idea, but for this problem, the worst case is always O(N).


  • 0
    H

    @haiwei624 you are right, thanks for your correction!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.