Find out how much is rotated using binary search.


  • 0
    J

    I noticed that in Search in Rotated Sorted Array I problem, many solutions in the Discuss Forum first find out how much the array has been rotated, then do a binary search. But for this problem, most solutions just do one binary search.

    If you are interested in how to find the first element in the original array, or how much this array has been rotated. Here I provide my binary-search implementation. The worst case time complexity is O(N), and average time complexity is O(logn).

    The basic idea is to find the index such that nums[index] > nums[index+1], and nums[index+1] is the element we want, index is how much rotated.

    class Solution {
    public:
        bool search(vector<int>& nums, int target) {
            if (nums.size() == 0) {
                return false;
            }
            int mod = nums.size();
            int begin = 0;
            int end = nums.size();
            int minIdx = 0; // if nums = [1,1,1,3,1], minIdx should be 4.
            while (begin < end) {
                if (begin + 1 == end) {
                    break;
                }
                int mid = (begin + end) / 2;
                if (nums[begin] < nums[mid]) { // nums[i] > nums[i+1]  does not hold for i in [begin, mid-1]
                    begin = mid;
                } else if (nums[mid] < nums[end - 1]) { // i in [mid, end-2] does not satisfy nums[i] > nums[i+1].
                    if (nums[end-1] > nums[end%nums.size()]) {
                        break;
                    } else { // end-1 does not satisfy
                        end = mid;
                    }
                } else if (nums[begin] > nums[mid]) { // i in [mid, inf] does not satisfy nums[i] > nums[i+1]
                    end = mid;
                } else if (nums[mid] > nums[end-1]) { // i in [begin, mid) does not satisfy nums[i] > nums[i+1]
                    begin = mid;
                } else { // nums[begin] == nums[mid] and nums[mid] == nums[end-1]
                    if (nums[begin] > nums[begin + 1]) {
                        break;
                    } else {
                        ++ begin;
                    }
                    if (nums[end-1] > nums[end%nums.size()]) {
                        break;
                    } else {
                        -- end;
                    }
                }
            }
            if (nums[begin] > nums[begin + 1]) {
                minIdx = (begin + 1)%nums.size();
            }
            if (nums[end-1] > nums[end%nums.size()]) {
                minIdx = end%nums.size();
            }
    
            begin = minIdx;
            end = begin + nums.size();
            while (begin < end) {
                int mid = (begin + end) / 2;
                if (nums[mid % mod] == target) {
                    return true;
                } else if (nums[mid % mod] < target) {
                    begin = mid + 1;
                } else {
                    end = mid;
                }
            }
            return false;
        }
    };
    

Log in to reply
 

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