Blind 75
Find Minimum in Rotated Sorted Array
- Problem
- LC 153
- Category
- Array
- File
- blind75_LC153FindMinimumInRotatedSortedArray.java
- Path
- pkg5leetcode/blind75/blind75_LC153FindMinimumInRotatedSortedArray.java
- Package
- pkg5leetcode.blind75
- Command
- java pkg5leetcode/blind75/blind75_LC153FindMinimumInRotatedSortedArray.java
- Approach
- Binary search on unsorted half.
- Complexity
- Time O(log n), Space O(1)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.blind75;2 3/*4 * Find Minimum in Rotated Sorted Array | LC 1535 * APPROACH: Binary search on unsorted half.6 * COMPLEXITY: Time O(log n), Space O(1)7 */8public class blind75_LC153FindMinimumInRotatedSortedArray {9 static int findMin(int[] nums) {10 int lo = 0, hi = nums.length - 1;11 while (lo < hi) {12 int mid = lo + (hi - lo) / 2;13 if (nums[mid] > nums[hi]) lo = mid + 1;14 else hi = mid;15 }16 return nums[lo];17 }18 19 public static void main(String[] args) {20 check(findMin(new int[]{3, 4, 5, 1, 2}) == 1, "case1");21 check(findMin(new int[]{4, 5, 6, 7, 0, 1, 2}) == 0, "case2");22 System.out.println("all tests passed");23 }24 25 static void check(boolean cond, String name) {26 if (!cond) throw new AssertionError("FAILED: " + name);27 System.out.println(" PASS " + name);28 }29}