【二分查找】旋转数组的最小数字

查找和排序

查找和排序都是经常用的，相对来说查找比较容易，一般就是顺序查找、二分查找、哈希表查找、二叉排序树查找。哈希表主要的优点是能在O(1)时间内查找某一元素，缺点是实现哈希表需要额外的空间。

排序比查找复杂，一般要掌握插入排序、冒泡排序、归并排序、快速排序、选择排序等，并能比较算法优劣。

面试题11:旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1。

这题是在二分查找基础上做了一些修改的，旋转后的两个子数组是各自有序的，而最小数字(旋转前的第一个数字)正是在两个子数组交界的位置：

和二分查找一样，设置两个指针(游标)分别指向第一个和最后一个元素，每次取中间元素。如果落在前一个子数组区间，就看后一半；如果落在后一个子数组区间，就看前一半。

这里”落在哪个子数组区间”可以通过和两个游标对应的元素值进行比较来判断。但是也存在特例，因为没有规定数组旋转前是严格递增的，旋转后可能形成这样的数组：

这种时候只能顺序查找来寻找最小元素。

另外，”旋转”可以是将前面0个数字拿到后面，所以只要判断第一个数字小于最后一个数字时，第一个数字就是最小的，直接返回。

#include<bits/stdc++.h>
using namespace std;

// 参数:
//        numbers:     要查找的数组首地址
//        index1:      查找的起始游标
//        index2:      查找的结束游标
// 返回值:
//        找到的最小数字
int MinInOrder(int* numbers, int index1, int index2) {
    int result = numbers[index1];//从起始游标处开始
    //遍历整个游标范围
    for(int i = index1 + 1; i <= index2; ++i) {
        //如果发现比当前result更小的数
        if(result > numbers[i])
            result = numbers[i];//记录之
    }
    return result;//最终找到的就是最小的 
}


// 参数:
//        numbers:     旋转后的数组首地址
//        length:      数组的长度
// 返回值:
//        找到的最小数字
int Min(int* numbers, int length) {
    //输入合法性校验
    if(numbers == nullptr || length <= 0)
        throw new exception();

    int index1 = 0;//初始化游标P1
    int index2 = length - 1;//初始化游标P2
    int indexMid = index1;//indexMid最终将指向数组中最小的数,初始化为一个数
    //这样在这个循环前判断,如果发现数组中第一个数小于最后一个数,就可以直接返回第一个数
    while(numbers[index1] >= numbers[index2]) {
        //[找到最小数的条件]
        //如果index1和index2指向相邻的两个数
        //则index1指向第一个递增子数组的最后一个数字
        //index2指向第二个子数组的第一个数字,也就是数组中的最小数字
        if(index2 - index1 == 1) {
            indexMid = index2;//记录下index2为所求
            break;
        }

        //如果下标为index1、index2和indexMid指向的三个数字相等
        //则只能顺序查找,因为无法判断该走向哪一边
        //但能确定一定还在[index1,inedx2]这个游标区间内
        indexMid = (index1 + index2) / 2;
        if(numbers[index1] == numbers[index2] && numbers[indexMid] == numbers[index1])
            return MinInOrder(numbers, index1, index2);//返回顺序查找的结果

        //缩小查找范围
        //如果中间数不小于P1数,说明分界点在后面
        if(numbers[indexMid] >= numbers[index1])
            index1 = indexMid;//所以将P1后移
        //如果中间数不小于P2数,说明分界点在前面面
        else if(numbers[indexMid] <= numbers[index2])
            index2 = indexMid;//所以将P2前移
    }
    return numbers[indexMid];//最终,中间数点就是分界点,即为所求
}

int main(){
    int array[] = { 3, 4, 5, 1, 2 };
    try{
        cout<<Min(array,5)<<endl;
    }catch(...){
        cerr<<"Invalid parameters"<<endl;
    }
    return 0;
}