旋转数组的概念:把一个数组最开始的若干个元素搬到数组的末尾,我们称为数组的旋转。例如{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