Super simple and clean Java, binary search.


  • 29
    J
    public int findMin(int[] nums) {
    	 int l = 0, r = nums.length-1;
    	 while (l < r) {
    		 int mid = (l + r) / 2;
    		 if (nums[mid] < nums[r]) {
    			 r = mid;
    		 } else if (nums[mid] > nums[r]){
    			 l = mid + 1;
    		 } else {  
    			 r--;  //nums[mid]=nums[r] no idea, but we can eliminate nums[r];
    		 }
    	 }
    	 return nums[l];
    }

  • 0
    E
    This post is deleted!

  • 1
    W

    hi, wujin, would you mind shedding some light on how you come up with the idea of comparing with the upper bound to decide the action, instead of the lower bound or nums[0]? not that straightforward for me though. Looking back it is a great solution, but how you find out comparing with the upper bound is the best way to go?


  • 0
    F

    Basically your solution runs in O(n) time, NOT in O(log(n)).
    If the array has different values in first and last position, algorithm can runs in O(log(n)), on the other hand should be O(n).


  • 0
    R

    @fabian4 this is the same as searching in rotated array II . the big O runtime will be linear considering worst case of all duplicates. You cant do better than O(N) in worst case.


  • 0
    O

    @weiyi3 I guess the reason is mid = start + (end -start)/2 implies and mid is always not equal to end.


  • 0
    G

    @oneexy
    The reason of using mid = start+(end-start)/2 is:
    because sometimes when you want to find mid of x and y such that x and y are very large numbers so it goes out of the range of int.


Log in to reply
 

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