C++程序判断数组是否排序且旋转

1. 问题描述

给定一个旋转排序数组，要求写一个C++程序来判断该数组是否经过旋转且排序，例如{3, 4, 5, 1, 2}即为已排序并旋转数组，{1, 2, 3, 4, 5}即为非旋转数组。

2. 思路分析

由于该旋转排序数组经过旋转，我们将其末尾的元素移到首位，使其形成一个非降序的数组，例如{1, 2, 3, 4, 5, 6, 7}被旋转成了{5, 6, 7, 1, 2, 3, 4}，我们可以发现，如果数组是未被旋转的，我们可以用二分法来判断某一数是否在其中，但题目要求的是旋转且排序的数组，因此本题基于这个思路，考虑寻找旋转的位置，即数组中的最小值。

具体步骤如下：

找到数组的中间元素mid，如果mid比mid+1大，那么mid+1即为最小值，停止寻找；
如果mid比mid-1小，那么mid即为最小值，停止寻找；
如果mid比首元素大，那么最小值在mid的右边，找mid+1到end之间的最小值；
如果mid比首元素小，那么最小值在mid的左边，找start到mid-1之间的最小值。

根据以上思路，我们即可写出代码。

3. 代码实现

下面是完整的C++代码实现，含有详细的注释：

#include<bits/stdc++.h> //万能头文件
using namespace std;

int findMin(int arr[], int n) {
    int low = 0, high = n - 1;

    while (high > low) {

        //计算中间元素
        int mid = (high + low) / 2;

        //mid比mid+1大，mid+1即为所求
        if (arr[mid] > arr[mid + 1])
            return arr[mid + 1];

        //mid比mid-1小，mid即为所求
        if (arr[mid] < arr[mid - 1])
            return arr[mid];

        //右边是有序数组，最小值在右边
        if (arr[mid] < arr[high])
            high = mid - 1;

        //左边是有序数组，最小值在左边
        else
            low = mid + 1;
    }
    return arr[low];
}

int main() {
    int arr[] = { 6, 7, 8, 1, 2, 3, 4, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "数组中的最小值为:" << findMin(arr, n);

    return 0;
}