首页 > 其他 > 详细

旋转数组的最小数字(改进版算法)

时间:2014-04-12 12:40:11      阅读:483      评论:0      收藏:0      [点我收藏+]
#include<iostream>
using namespace std;
//directly sort if the array has repeat value
int drctsort(int a[],int length)
{
int resu=a[0],i;
for(i=0;i<length;i++)
if(a[i]<resu) resu=a[i];
return resu;
}
//core algorithm
int minvalue(int a[],int length)
{
int beg=0,end=length-1,mid;
if(a[beg]<a[end]) return a[beg];
while(true){
if((end-beg)==1) break;
mid=(beg+end)/2;
if(a[beg]<a[mid]) beg=mid;
else if(a[mid]<a[end]) end=mid;
else return drctsort(a,length);
}
return a[end];
}
int main()
{
int a[]={1,1,1,0,1};
int b[]={1,0,1,1,1};
int c[]={2,3,4,5,0,1};
int resu=minvalue(a,5);
cout<<"min number:"<<resu<<endl;
resu=minvalue(b,5);
cout<<"min number:"<<resu<<endl;
resu=minvalue(c,6);
cout<<"min number:"<<resu<<endl;
return 0;
}

概念说明:旋转数组 : 把一个数组最开始的若干元素搬到数组末尾。

原题:输入一个递增排序数组的一个旋转,输出旋转数组的最小元素。

旋转数组的最小数字(改进版算法),布布扣,bubuko.com

旋转数组的最小数字(改进版算法)

原文:http://blog.csdn.net/pyz_tech/article/details/23450655

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