求局部最大值问题：
给定一个无重复元素的数组A[0...N-1]，找到一个该数组的局部最大值。
问题分析：
遍历一遍得全局最大值，它显然是局部最大值，但是时间复杂度是O(n),现在要求时间复杂度为O(logn)。
问题求解过程类似于二分查找，但是还不完全一样，需要分析清楚问题来源。问题中只需要求出一个局部最大值，并且数组中不考虑重复的元素。
因此，可以每次取中间点，当A[mid] > A[mid+1] 丢弃后半段，right = mid; 当A[mid] < A[mid+1]，丢弃前半段，left = mid+1。
程序实现：
1 /*************************************** 2 FileName LocalMaxiNum.cpp 3 Author : godfrey 4 CreatedTime : 2016/5/3 5 ****************************************/ 6 #include <iostream> 7 #include <cstring> 8 #include <vector> 9 #include <algorithm> 10 #include <stdio.h> 11 #include <stdlib.h> 12 13 using namespace std; 14 15 int LocalMaxiNum(const int* A,int size){ 16 int Left = 0; 17 int Right = size - 1; 18 int mid; 19 while(Left < Right){ 20 mid = (Left + Right) / 2; 21 cout<<"mid : "<<mid<<" Left : "<<Left<<endl; 22 if(A[mid] < A[mid+1]){ 23 Left = mid + 1; 24 } 25 else{ 26 Right = mid; 27 } 28 } 29 return A[Left]; 30 } 31 int main() 32 { 33 int a[] = {1,2,3,4,5,3,2,0,3,4,7,6,5}; 34 int LocMaxNum = LocalMaxiNum(a,sizeof(a)/sizeof(int)); 35 cout<<"one LocalMaxiNum : "; 36 cout<<LocMaxNum<<endl; 37 return 0; 38 }
运行结果：
转载请注明出处：
C++博客园：godfrey_88