Super simple and clean Java, binary search.

  • 29
    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
    This post is deleted!

  • 1

    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

    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

    @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.

Log in to reply

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