# Java solution with binary search

• The minimum element must satisfy one of two conditions: 1) If rotate, A[min] < A[min - 1]; 2) If not, A[0]. Therefore, we can use binary search: check the middle element, if it is less than previous one, then it is minimum. If not, there are 2 conditions as well: If it is greater than both left and right element, then minimum element should be on its right, otherwise on its left.

``````public class Solution {
public int findMin(int[] num) {
if (num == null || num.length == 0) {
return 0;
}
if (num.length == 1) {
return num[0];
}
int start = 0, end = num.length - 1;
while (start < end) {
int mid = (start + end) / 2;
if (mid > 0 && num[mid] < num[mid - 1]) {
return num[mid];
}
if (num[start] <= num[mid] && num[mid] > num[end]) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return num[start];
}
}``````

• {
class Solution {
public:
int findMin(vector<int> &num) {
sort(num.begin(),num.end());
return num[0];
}
};
}

• Why have O(nlogn) when you can do it in log(n)

• ``````public class Solution {
public int findMin(int[] nums) {
int lo = 0, hi = nums.length - 1;
if (nums[hi] > nums[lo]) return nums[lo];
while (hi - lo > 1) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] < nums[lo]) {
hi = mid;
} else {
lo = mid;
}
}
return Math.min(nums[lo],nums[hi]);
}
}``````

• Nice answer! One thing want to point out is when calculating mid, (start + end) may potentially over flow. So like the first answer below using
mid = lo + (hi - lo) / 2;
would avoid that.

• Nice solution! I'm confused about this sentence "end=mid-1" why not return start=mid-1. For example '6 7 0 1 2 4 5': mid is 1, and when start=mid-1, return nums[start]=0

• ``````public int findMin(int[] nums) {
int left = 0;
int right = nums.length - 1;
while(left < right) {
int mid = left + (right - left) / 2;
if(nums[mid] < nums[right]) {
right = mid;
} else {
left = mid + 1;
}
}
return nums[left];
}
``````

simpler Java code

• ``````    public int findMin(int[] nums) {
int previous=nums[0];
for(int i=1;i<nums.length;i++)
{
if(previous>nums[i])
return nums[i];
else
{
previous=nums[i];
}
}
return nums[0];
}
}
``````

any thing wrong with this one?

• int lo = 0, hi = nums.length - 1;
if (nums[hi] > nums[lo]) return nums[lo];
while (hi - lo > 1) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] < nums[lo]) {
hi = mid;
} else {
lo = mid;
}
}
return Math.min(nums[lo],nums[hi]);

for case {3,2,1}, this returns 2, but it passes OJ. Could you double check this?

• My version. Hope it helps

``````public class Solution {
public int findMin(int[] nums) {
int left = 0, right = nums.length-1;
while(left < right){
if(nums[left] < nums[right])
break;
int mid = (left + right)/2;
if(nums[mid] > nums[right]){
left = mid + 1;
}else{
right = mid;
}
}
return nums[left];
}
}
``````

• I don't think the check for `num[start] <= num[mid]` is necessary, if `num[mid] > num[end]`, it will always be the case that the minimum element will be on the right half.

My code:

``````public class Solution {
public int findMin(int[] nums) {
int min = nums[0];

int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = (left + right) / 2;

if (nums[right] < nums[mid])
left = mid + 1;
else if (mid > left && nums[mid - 1] < nums[mid])
right = mid - 1;
else {
min = nums[mid];
break;
}
}

return min;

}
}

``````

• @rilong1280 take ur trash away

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