9-line java code, beats 95.14% run times


  • 18
    M

    if the array is indeed rotated by some pivot, there are only 2 possibilities

    1. a[mid] > a[left] && a[mid] > a[right], meaning we are on the bigger part, the smaller part is on our right, so go right
    1. a[mid] < a[left] && a[mid] < a[right], meaning we are on the smaller part, to find the smallest element, go left

    if the array is not rotated (actually one rotating cycle completed), we just need to go left, in this case a[mid] < a[right] always holds.

    combining the cases above, we conclude that

    if a[mid] > a[right], go right; if a[mid] < a[right], go left.

    public class Solution {
        public int findMin(int[] nums) {
            if (nums==null || nums.length==0) { return Integer.MIN_VALUE; } 
            int left = 0, right = nums.length-1;
            while (left < right-1) {  // while (left < right-1) is a useful technique
                int mid = left + (right-left)/2;
                if (nums[mid] > nums[right]) { left = mid; }
                else { right = mid; }
            }
            if (nums[left] > nums[right]) { return nums[right]; }
            return nums[left];
        }
    }

  • 0
    D

    @mach7 why left<right-1 works?


  • 4
    M

    @dave24 well, this has nothing to do with the essential idea of the algorithm. it's just a trick, which could save you some trouble dealing with corner cases (left and right pointers' indices) during a binary search. "left < right - 1" means the search would stop when left == right - 1, that is, left and right are next to each other. so all you need to do is performing an additional check "if (nums[left] > nums[right]) { return nums[right]; }" after the while loop.


  • -1
    C

    We used the same algorithm. But I think you should add this line before the loop, otherwise, this algorithm fails in '1,2,3'.

    if (nums[0] < nums[right]) return nums[0];
    

  • 0
    M

    @channerduan hi. i dont think my code fails at test case 1 2 3. could you please elaborate?


  • 1
    C

    @mach7 Sorry, my fault. Your code compares mid with right, but my code compares mid with left. So your code automatically pushes boundary toward a minimum value and covers this case, which is neater than mine. Thanks a lot! I learned something! Is it a common trick that comparing with right side?


  • 1
    M

    @channerduan hi. i use following trick in binary search related problems to handle corner cases.

    1. left = 0, right = array.length - 1

    2. while (left < right - 1) {...} // stops at left == right - 1 -- left and right next to each other

    3. // after that, need to do one more comparison
      if (array[left] < array[right]) {...}
      else {...}


  • 0
    C

    @mach7 Thanks a lot!


  • 0
    M

    I don't understand how 1 and 2 lead to the conclusion. Why we ignore "a[mid] > a[left]" and "a[mid] < a[left]"?


  • 0
    M

    @MichaelWayne i guess it's because, for this particular problem,

    1. If the array is indeed rotated (for example [3, 4, 5, 6, 1, 2, 3])
      when a[mid] > a[right], a[left] < a[mid] is always true, that is, a[mid] > a[right] implies a[left] < a[mid]. so (a[mid] > a[right]) is equivalent to (a[mid] > a[right] && a[left] < a[mid]). GO RIGHT.
      when a[mid] < a[right], a[left] > a[mid] is always true, that is a[mid] < a[right] implies a[left] > a[mid]. so (a[mid] < a[right]) is equivalent to (a[mid] < a[right] && a[left] > a[mid]). GO LEFT.
      Therefore, all we need is to compare a[mid] and a[right].
    2. Actually we can also only compare a[mid] and a[left] in 1. but for unrotated array, we just need to go all the way left, and a[mid] < a[right] always holds. <-- this happens to be the same case in 1.

    in the end, we know we just need to compare a[mid] and a[right].


  • 0
    Y
    This post is deleted!

Log in to reply
 

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