# My pretty simple code to solve it

• ``````class Solution {
public:
int findMin(vector<int> &num) {
int lo = 0;
int hi = num.size() - 1;
int mid = 0;

while(lo < hi) {
mid = lo + (hi - lo) / 2;

if (num[mid] > num[hi]) {
lo = mid + 1;
}
else if (num[mid] < num[hi]) {
hi = mid;
}
else { // when num[mid] and num[hi] are same
hi--;
}
}
return num[lo];
}
};
``````

When num[mid] == num[hi], we couldn't sure the position of minimum in mid's left or right, so just let upper bound reduce one.

• a simple question: why mid = lo + (hi - lo) / 2 rather than mid = (hi + lo) / 2 ?

• This is a famous bug in binary search. if the size of array are too large, equal or larger than the upper bound of int type, hi + lo may cause an overflow and become a negative number. It's ok to write (hi + lo) / 2 here, leetcode will not give you a very large array to test. But we'd better know this. For a detailed information or history of this bug, you could search "binary search bug" on google.

• that makes sense, I'll google it, thank you!

• This method would be even slower than just loop through all the numbers btw hi and lo to check if they are all the same.

• I think in worst case no solution is better than O(n) complexity.

• Could you please explain the reason of hi-- more carefully?

• very concise and smart idea

• thanks very much~

• I suggest another golfing code using bit manipulation: `mid = (lo & hi) + ((lo ^ hi) >> 1)`: the first part accounts for the carry bit and the second part accounts for the sum bit. Since we need to divide by `2`, so the sum bit shifts to right by `1` and the carry bit simply does not shift (originally it needs to shift to left by `1`).

• Hi, namedfree. If you want to know how `hi--` works, I suggest you to run the above codes on the two examples `[1, 0, 1, 1, 1]` and `[1, 1, 1, 0, 1]` on the solution tag.

• 3Q,I have understood.

• I am confused on using

• while (lo < hi) ... hi = mid;
• while (lo <= hi) ... hi = mid-1;

in which case use each?

• This code is correct to return the minimum value of the array. But in terms of "find the minimum value index" it is not right.
Consider this case: 1 1 1 1 1 1 1 1 2 1 1
the min index returned is 0, while actually it should be 9.
For this case: 2 2 2 2 2 2 2 2 1 2 2
it will return the correct index, which is 8.

The reason is, the pivot index will be passed by at hi--. To avoid this, we can add the following judgement:

else {

``````if (nums[hi - 1] > nums[hi]) {
lo = hi;
break;
}
hi--;
``````

}

• Hi, benlong. Why do you say in cases `[1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1]` we should return `9`? I think it is Ok to return the first index of the minimum, which is just `0`. Moreover, where do you get this `9`: the `9`-the element is neither the first minimum nor the last minimum...

• Hi jiaochao,

I didn't say this approach is wrong. To solve this particular problem it's absolutely correct and enough.

What I was trying to say, however, is that it would be better if we can return exactly the 1st minimum value index, which is 9 in this case. The significance of this index lies in that it is also the number of shifts we have done to rotate the original normal sequence [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2] to the non-sorted form. That is to say, 9 is the offset of all elements from their normal positions.

With this offset, we can easily solve the other closely related problem [Search in Rotated Sorted Array II] with unified one pass binary search:

``````    //hi is the offset we found in previous step, omitted here;
int offset = hi;
lo = 0;
hi = n - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
//please note the mapping from logical mid to realMid in rotated array
int realMid = (mid + offset) % n;
if (nums[realMid] == target) {
return true;
} else if (nums[realMid] < target) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}

return false;``````

• This post is deleted!

• Love the phrases "3Q, I have understood." and "we couldn't sure".

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