O(lgN) with worst case of O(N)


  • 2
    L
    public bool Search(int[] nums, int target) {
        int sIndex = 0, left = 0, right = nums.Length - 1;
        //1. find the smallest element O(lgN) with worst O(N)
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] > nums[right]) left = mid + 1;
            else if (nums[mid] < nums[right]) right = mid;
            else
                while (right > mid && nums[right] == nums[mid]) right--;
                if (right != mid) {
                    if (nums[right] > nums[mid]) left = ++right;
                    else left = right;
                }
        }
        sIndex = nums[right] > nums[0] ? 0 : right;
        //2. Identify the value range
        if (sIndex != 0 && target >= nums[0]) { left = 0; right = sIndex - 1; }
        else { left = sIndex; right = nums.Length - 1; }
        //3. Binary search it O(lgN)
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) return true;
            else if (nums[mid] > target) right = mid - 1;
            else left = mid + 1;
        }
        return false;
    }

Log in to reply
 

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