剑指 Offer 11. 旋转数组的最小数字
本题的作法是二分法。具体做法是：左右区间根据number[r]（右端点）进行区分，利用左区间大于等于number[r],右区间小于等于number[r]的特性。
在此基础上，二分法得以适用。
本题的一个大坑：
二分法的中点，numbers[mid]，能否与numbers[l]（左端点）作比较？
答案是：可以，但是要特别防范最小值就是numbers[l]的情况。
本题最好与numbers[r]作比较。
class Solution { public: int minArray(vector<int>& numbers) { if(numbers.size() == 0) return 0; int l = 0, r = numbers.size() - 1; while(l < r) { int mid = l + (r - l) / 2; // 左右区间根据number[r]进行区分，左区间大于等于number[r],右区间小于等于number[r]的特性 if(numbers[mid] < numbers[r]) r = mid; else if(numbers[mid] > numbers[r]) l = mid + 1; else r -= 1; } return numbers[l]; } };
如果与numbers[l]（左端点）进行比较，也是可以的，但是每次循环都要特别判断最小值就在区间最左边的情况（例如[1 2 3 4 5]）:
class Solution { public: int minArray(vector<int>& numbers) { if(numbers.size() == 0) return 0; int l = 0, r = numbers.size() - 1; while(l < r) { // 如果用numbers[l]来区分，则区分依据还是左区间大于等于number[l],右区间小于等于number[l] // 但是如果最小值就在number[l]处,例如[1 2 3 4 5]，那么计算出的number[mid]一定是大于numbers[l]的，但是此时numbers[mid]在右区间，与区分依据违背 // 因此,以numbers[l]作区分依据需要每次循环都判断numbers[l]<numbers[r]。 if(numbers[l] < numbers[r]) return numbers[l]; int mid = l + (r - l) / 2; if(numbers[mid] < numbers[l]) r = mid; else if(numbers[mid] > numbers[l]) l = mid + 1; else l = l + 1; } return numbers[l]; } };
tips:
// 当l和r非常大时，mid有可能会溢出 mid = (l + r) / 2 // 解决方案： mid = l + (r - l) / 2