题解 | 左闭右开型二分查找，图解生动形象，C语言实现 [罅隙]
旋转数组的最小数字
http://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba
解题思路
1)为什么想到二分查找？
二分查找的本质的本质是二段性，只要满足二段性的问题都可以使用二分查找求解。在本题中二分查找的二段性体现在：最小值左边的单调增，最小值右边的单调增。且左边的元素都大于右边的元素。
2)如何解决分段单调的问题？
很简单，我们只需要比对arr[mid]与arr[0]和arr[numsSize - 1]的大小关系就可以：
- arr[mid] > arr[0],说明mid此时落在最小值左边
- arr[mid] < arr[numsSize - 1]，说明此时mid落在最小值的右边。
根据这一特性我们利用左闭右开型的二分查找就可以压缩出最小值所在的地方。对于左闭右开，链接左开右闭型二分查找不熟的同学可以看看我之前写过的博客【玩转二分查找Ⅰ】左闭右闭型，左开右闭型，左闭右开型（动图演绎）
到此我们可以写下这样的一段代码
int minNumberInRotateArray(int* arr, int arrSize)
{
int left = 0;
int right = arrSize - 1;
while(left < right)
{
int mid = (left + right) / 2;
if(arr[mid] >= arr[0])
{
left = mid + 1;
}
else
{
right = mid;
}
}
return arr[left];
}
3)遗憾的是上面的写法是错误的。为什么呢？
因为题目只是说到非降序，所以不能排除出现重复的情况：
4)如何解决重复的问题?
我们重点对数据的右边进行去重
- 如果发生arr[mid] < arr[right],则和上面一样使得right = mid
- 如果发生arr[mid] > arr[right],则和上面一样使得left = mid + 1
- 如果发生arr[mid] == arr[right],则说明发生重复，对于重复我们将right--，因为既然有重复，那删掉其中一个可以保证至少还有1个
这样不断删之后可以排除重复的影响，最终的代码如下
最终代码
int minNumberInRotateArray(int* arr, int arrSize)
{
int left = 0;
int right = arrSize - 1;
while(left < right)
{
int mid = (left + right) / 2;
if(arr[mid] < arr[right])
right = mid;
else if(arr[mid] > arr[right])
left = mid + 1;
else
right -= 1;
}
return arr[left];
}
查看14道真题和解析
虽然我也是抄的