LeetCode Q153: Find Minimum in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

Solution:

Binary search, each step move to branch where numbers are not in order. Need to consider the case where the given array is already sorted.

	class Solution {
	public:
	int findMin(vector<int>& nums) {
	int l=0;
	int r=nums.size()-1;
	while(l<r){
	int mid=(l+r)/2;
	if(l==mid||r==mid)
	return min(nums[l], nums[r]);
	if(nums[mid]>nums[r]){
	l=mid;
	continue;
	}
	if(nums[mid]<nums[l]){
	r=mid;
	continue;
	}
	if(nums[l]<nums[r])
	break;
	}
	return nums[l];
	}
	};

view raw Q153MinInRotatedArray.cpp hosted with ❤ by GitHub

Round 2 solution: Questions like this, remember to illustrate all possible cases on paper first. It is easier to separate all cases from those examples.
For this question, find the middle element, and drop half of elements every iteration.

	class Solution {
	public:
	int findMin(vector<int>& nums) {
	int res;
	if(nums.empty())
	return 0;
	int l = 0;
	int r = nums.size()-1;
	while(l<r-1){
	int mid = (l+r)/2;
	if(nums[l]<nums[mid])
	if(nums[mid]<nums[r])
	r=mid;
	else
	l=mid;
	else
	r=mid;
	}
	res = min(nums[l], nums[r]);
	return res;
	}
	};

view raw Q153Rnd2.cpp hosted with ❤ by GitHub

Round 2 solution: For questions like this one, first list all examples on paper. It is easier to separate all cases from those examples.
For this question, we find middle element every time and we decide which type of order the current array is. Then we can drop half of elements depends on the pattern we get from examples we listed on the paper.

	class Solution {
	public:
	int findMin(vector<int>& nums) {
	int res;
	if(nums.empty())
	return 0;
	int l = 0;
	int r = nums.size()-1;
	while(l<r-1){
	int mid = (l+r)/2;
	if(nums[l]<nums[mid])
	if(nums[mid]<nums[r])
	r=mid;
	else
	l=mid;
	else
	r=mid;
	}
	res = min(nums[l], nums[r]);
	return res;
	}
	};

view raw Q153Rnd2.cpp hosted with ❤ by GitHub