首页 > 其他 > 详细

求旋转数组中的最小值

时间:2014-02-20 01:34:54      阅读:260      评论:0      收藏:0      [点我收藏+]

旋转数组的概念:把一个数组最开始的若干个元素搬到数组的末尾,我们称为数组的旋转。例如{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。

解法用到了二分查找法。

有一种特殊情况下如果二分法所指向的三个元素都相等,就不能用二分查找法了,就要用顺序查找。

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <cstdlib>
using namespace std;
 
int Min(int numbers[],int length)
{
    if(length<=0)
      {
          cout<<"invalid length"<<endl;
          exit(-1);
      }
    int index1=0;
    int index2=length-1;
    int mid=index1;
    while(numbers[index1]>=numbers[index2])
        {
           if(index2-index1==1)
             {
                 mid=index2;
                 break;
             }
            mid=(index1+index2)/2;
            if(numbers[index1]<=numbers[mid])
                   index1=mid;
            else if(numbers[index2]>=numbers[mid])
                   index2=mid;
        }
        return numbers[mid];
}
    int main()
    {
          int arr[]={3,4,5,1,2};
          int arr2[]={3,4,5,1,2,3};
          int min1,min2;
          min1=Min(arr,5);
          min2=Min(arr2,6);
          cout<<"最小元素分别是"<<min1<<","<<min2<<endl;
          return 0;
    }

求旋转数组中的最小值

原文:http://www.cnblogs.com/xshang/p/3556062.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!