Advertisement
aero2146

Find Minimum in Rotated Sorted Array

Dec 29th, 2019
128
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 0.74 KB | None | 0 0
  1. /*
  2. Explanation:
  3. Using a modified binary search to complete this in O(nlogn) time.
  4. */
  5.  
  6. class Solution {
  7.     public int findMin(int[] nums) {
  8.         int l = 0;
  9.         int r = nums.length-1;
  10.        
  11.         if (nums[0] <= nums[nums.length-1]) return nums[0];
  12.        
  13.         while (l < r) {
  14.             int m = (l+r)/2;
  15.            
  16.             if (m != 0 && nums[m] < nums[m-1]) return nums[m];
  17.             if (m != nums.length-1 && nums[m] > nums[m+1]) return nums[m+1];
  18.            
  19.             // On the left side and need to move right to hit pivot
  20.             if (nums[m] > nums[l]) {
  21.                 l += 1;
  22.             } else if (nums[m] < nums[l]) {
  23.                 r -= 1;
  24.             }
  25.         }
  26.         return 0;
  27.     }
  28. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement