# C++ 4ms binary search with some comments

• ``````// Lets represent rotated array 4567890123 as:
//             9
//           8    <--- top middle
//         7
//       6
//     5
//   4
//  -0-1-2-3-4-5-6-7-8-9- [index] in array
//                     3
//                   2
//                 1    <--- bottom middle
//               0
// When you do binary search your middle index is either on the "top" or "bottom" index
// when l == 0 and r == 9 then mid == 4, mid_number == nums[mid] == 8
// I call it "top middle", since it always > than both nums[l] and nums[r] (4 < 8 > 3)
// so the min value is on the right side of it
// when l == 4 and r == 9 then mid == 7, mid_number == nums[mid] == 1
// I call it "bottom middle" since it always < than both nums[l] and nums[r] (8 > 1 < 3)
// so the min value is somewhere on the left side of it
int findMin(vector<int>& nums)
{
int l = 0, r = nums.size() - 1;
while(r - l > 1)
{
int mid = (l + r) / 2;
if(nums[l] < nums[mid] && nums[mid] > nums[r])
{
l = mid; // top middle, min value is somewhere on the right
}
else
{
r = mid; // bottom middle, min value is somewhere on the left
}
}

return min(nums[l], nums[r]);
}``````

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