private: intfindMin(const vector<int>& nums, int lo, int hi) { // only one element if (lo == hi) return nums[lo];

if (isSorted(nums, lo, hi)) return nums[lo]; int mid = lo + (hi - lo) / 2; int left = findMin(nums, lo, mid); int right = findMin(nums, mid + 1, hi); returnmin(left, right); }

boolisSorted(const vector<int>& nums, int lo, int hi) { return nums[lo] < nums[hi]; // must be < (<= will fail in the case [3, 1, 3]) }

Time: $O(\log{N})$

False: $T(N) = 2T(N/2) = O(N)$ ❌

At each level, at least one side could be done in $O(1)$.

True: $T(N) = O(1) + T(N/2) = O(\log{N})$

Space: $O(\log{N})$

Binary Search

The basic idea is that if nums[mid] >= nums[lo] we assure that the inflection point is on the right part.

However, unlike the solution in 153, we need 3 cases:

private: intfindMin(const vector<int>& nums, int lo, int hi) { // only one element if (lo == hi) return nums[lo]; // the subarray is sorted if (nums[lo] < nums[hi]) return nums[lo]; int mid = lo + (hi - lo) / 2;

public: intfindMin(vector<int>& nums) { int lo = 0; int hi = nums.size() - 1; // stops when there is only one element // in other words, it makes sure that there are at least 2 elements while (lo < hi) { if (nums[lo] < nums[hi]) return nums[lo]; int mid = lo + (hi - lo) / 2; if (nums[mid] > nums[lo]) { lo = mid + 1; } elseif (nums[mid] > nums[lo]) { hi = mid; } else { // ??? } } return nums[lo]; }

Time: $O(\log{N})$

In the worst case scenario it would become $O(N)$.

Space: $O(\log{N})$

Comment

Junhao Wang

Hi, I was a master student at USC studying Computer Science.