Summary: search in rotated sorted array (with/without duplicates). Java Solution


  • 1

    "Binary search is the easiest hardest problem."

    I spent a while trying to think of an idea that could solve both this problem and also the problem with duplicates, and here are my solutions. Hope it would help:)

    1. Let's first talk about the problem without duplicates (which I believe is easier). The key is to find the sorted half part of the array.
    public class Solution {
        public int search(int[] nums, int target) {
            int left = 0, right = nums.length-1; 
            while (left <= right) {
                if (left == right)  
                    return nums[left] == target ? left:-1; 
                int mid = left + (right - left)/2; 
                if (nums[mid] == target) return mid; 
                if (nums[mid] <= nums[right]) {
                    if (target > nums[mid] && target <= nums[right]) {
                        left = mid + 1; 
                    } else {
                        right = mid - 1; 
                    }
                } else {
                    if (target >= nums[left] && target < nums[mid]) {
                        right = mid - 1; 
                    } else {
                        left = mid + 1; 
                    }
                }
            }
            return -1; 
        }
    }
    
    1. As for the problem with duplicates, we only need to modify a few lines in the solution above. The most significant change is that we need to specifically discuss the case where nums[mid] == nums[right]:
    public class Solution {
        public boolean search(int[] nums, int target) {
            int left = 0, right = nums.length - 1;
            while ( left <= right) {
                if (left == right)
                    return nums[left] == target; 
                int mid = left + (right-left)/2; 
                if (nums[mid] == target) {
                    return true; 
                }
                if (nums[mid] < nums[right]) {
                    if (target > nums[mid] && target <= nums[right]) {
                        left = mid + 1; 
                    } else {
                        right = mid - 1; 
                    }
                } else if (nums[mid] > nums[right]) {
                    if (target >= nums[left] && target < nums[mid]) {
                        right = mid - 1; 
                    } else {
                        left = mid + 1; 
                    }
                } else if (nums[mid] == nums[right]) {
                    right--; 
                }
            }
            return false; 
        }
    }
    

  • 0
    M

    Thanks for sharing.

    But, regarding the one with duplicates handling,
    could you explain, "else if (nums[mid] > nums[right])" a little?
    I know it means the left part of the array is sorted,
    but why "nums[mid] > nums[left]" doesn't work?


  • 0

    It's because when mid == left (which would happen occasionally since divide in java is rounding down), the left half is sorted, but it would not satisfy the condition nums[mid] > nums[left]. Then it means we might need to go to the last condition, which leads to right--. (for example, cases like [1,3], given target = 3).


Log in to reply
 

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