面试程序题-二分查找(1)

一个数组,大小先减后增,请找到增减部分的分界点,要求算法时间复杂度O(logN)。

下面给出了一个递归实现的版本。

这个问题还可以让查找其中的某个元素,也是二分,思路一样。

#include <iostream>

#define MAX 13
using namespace std;
void findBreakpoint(int* a, int starti, int endi){
int i = (endi-starti)/2+starti;
if(starti==i){
cout<<i<<endl;
return;
}
if(a[i]<a[i+1]){
findBreakpoint(a, starti, i);
}else{
findBreakpoint(a, i+1, endi);
}
}

int main(){
int a[MAX] = {12, 11, 10, 8, 5, 6, 7, 9, 11, 12, 13, 20, 50};
findBreakpoint(a, 0, MAX-1);

return 0;
}