二分查找经典题

—寻找旋转排序数组中的最小值

二分查找，是一种非常高效的算法，它能够在一个有序数组中查找指定的值。这里要介绍的是二分查找在寻找旋转排序数组中的最小值中的应用。这是一个经典问题，因为它能够展现出二分查找的高效性以及对于问题的分析思维。

问题描述

假设一个按照升序排列的数组在预先未知的某个点上进行了旋转。例如:

原数组：{0,1,2,4,5,6,7}

旋转后数组：{4,5,6,7,0,1,2}

请找出其中最小的元素。

分析思路

求解这个问题的关键是如何使用二分查找。我们可以通过比较中间点和两端点的大小关系，来判断最小值所在的区间。以旋转后的数组{4,5,6,7,0,1,2}为例，不同的中间点对于最小值的影响如下所示：

（1）当中点值mid > 最右端点值right，说明最小值在mid和right之间。如图：

（2）当中点值mid < 最右端点值right，说明最小值在left和mid之间。如图：

（3）当中点值mid = 最右端点值right，无法判断最小值在哪一段，但原问题中的最右值显然不是最小值，故我们可以排除最右值，继续二分查找。如图：

根据上述的思路，我们可以写出以下的代码：

int findMin(int* nums, int numsSize) {

int left = 0;

int right = numsSize - 1;

while (left < right) {

int mid = left + (right - left) / 2;

if (nums[mid] > nums[right]) {

left = mid + 1;

} else {

right = mid;

}

}

return nums[left];

}

时间复杂度为O(log n)。

注意事项

在求解这个问题的时候，需要注意以下几点：

- 特判：当数组长度为1时，最小值就是该元素；

- 特判：当数组已经是有序的，最小值就是数组中第一个元素；

- 由于mid的计算方式，left和right的值也可能相等。在这种情况下，最小值就是数组中left或right所在的位置。

总结

在分析和求解旋转排序数组中的最小值的过程中，我们深入了解了二分查找。我们发现，二分查找可以用来解决许多问题，而且这样的算法高效简单。当我们遇到问题时，应该首先考虑使用它来解决。