现在的位置: 首页 > 综合 > 正文

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个排好序的数组的一个旋转。输出旋转数组的最小值。

2014年09月05日 ⁄ 综合 ⁄ 共 529字 ⁄ 字号 评论关闭

题目:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个排好序的数组的一个旋转。输出旋转数组的最小值。

举例:输入数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转,该数组的最小值为1。

答:

复制代码
#include "stdafx.h"
#include <iostream>

using namespace std;

//查找旋转数组中的最小元素
int FindMinValue(int arr[], int length)
{
    int low = 0;
    int high = length - 1;
    while (low < high)
    {
        if (high - low == 1)
        {
            return arr[high];
        }
        int mid = (low + high) / 2;
        if (arr[mid] >= arr[low])
        {
            low = mid;
        }
        else if (arr[mid] <= arr[high])
        {
            high = mid;
        }
    }
    return -1;
}

int _tmain(int argc, _TCHAR* argv[])
{
    int arr[] = {8, 9, 10, 1, 2, 3, 4, 5, 6 , 7};
    cout<<FindMinValue(arr, sizeof(arr)/sizeof(arr[0]))<<endl;
    return 0;
}
复制代码

界面运行如下:

抱歉!评论已关闭.