Leetcode BinarySearch Template II Find Minimum in Rotated Sorted Array

user_2755407 0
Viewed 249

I am trying to solve the question in template 2 of Binary Search..Find Minimum in Rotated Sorted Array. The question is as below:

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

[4,5,6,7,0,1,2] if it was rotated 4 times.
[0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums, return the minimum element of this array.

Example 1:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:

Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:

Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.

Constraints:

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
All the integers of nums are unique.
nums is sorted and rotated between 1 and n times.

My solution code is as below:

public int findMin(int[] nums) {
        
        if(nums == null || nums.length == 0) {
            return -1;
        }
        
        if(nums.length == 1) return nums[0];

        if(nums.length == 2) {
    
            return (nums[0] > nums[1])? nums[1]:nums[0]; 
    
        }

        int left = 0;
        int right = nums.length;
        
        while(left < right) {
            
            int mid = left + (right - left)/2;
            
            // [3,4,5,1,2]
            if(nums[mid] >  nums[mid + 1]) {
                
                return nums[mid + 1];
            
            } else if(nums[mid] <  nums[mid + 1]) {
                
                right = mid;
                
            }
            
        }
        
        if(left != nums.length) {
            
            return nums[left];
            
        }
        
        return -1;
}

My code is working for the sample sets below:

nums = [3,4,5,1,2]
nums = [4,5,6,7,0,1,2]
nums = [11,13,15,17]
nuts = [4,5,6,7,0,1,2]

But when I try to submit the code, I am getting the error as below:

Runtime Error Message:
java.lang.ArrayIndexOutOfBoundsException: Index 1 out of bounds for length 1
  at line 16, Solution.findMin
  at line 54, __DriverSolution__.__helper__
  at line 84, __Driver__.main
Last executed input:
[1]

Can anyone please pinpoint the flaw in my coding logic?

Edit: I added two cases(for nums.length == 1 or 2) in my solution.

if(nums.length == 1) return nums[0];

if(nums.length == 2) {
    
    return (nums[0] > nums[1])? nums[1]:nums[0]; 
    
}

but still I am getting error for the case when nums = [2, 3, 4, 5, 1]..i.e I am getting the result value 2, but original answer will be 1.

binary-search java
1 Answers

Bug

The mid of your array

int[] mid = {1, 2, 3, 4, 5}

Should be the third element so mid=3

The mid is wrong calculated.
For example in your first iteration left=0 and right=5 So the result of the following calculation is

int mid = left + (right - left)/2
// result -> mid=2

Reason
Because you assign the result to an integer the decimal part will be lost. The result is instead of 2,5 => 2

Round Up

The following function will round up your result so you calculate the right mid value

public static long roundUp(long num, long divisor) {
    return (num + divisor - 1) / divisor;
}

Call the function with

int mid = (int)YourClass.roundUp((left + (right - left)), 2);

Additional Cases

You have to consider the cases when the length is 1 and the length is two

if(nums == null || nums.length < 1) {
            return -1;
} else if(nums.length == 1){
  // you don't have to apply a binary search there is only one element
  // you can directly return it
  return nums[0];
} else if(nums.length == 2){
  return nums[0] < nums[1]? nums[0] : nums[1]; 
}
user_147470390
Related