可采用二分查找的思路，优先搜索中间元素，判断其是否大于左右两边的元素，若是，直接返回该元素。否则，判断该元素与相邻元素的上升或下降趋势，若上升，保留右半边。若下降，保留左半边，继续重复上述过程，直到元素数小于3停止递归调用。
代码
//给定含有n个不同数的数组L={x1,x2,…,xn}，如果L中存在xi，使得x1<x2<…<xi-1<xi>xi+1>…>xn， // 则称L是单峰的，并称xi是L的峰顶。假设L是单峰的，设计一个优于O(n)的算法找到L的峰顶。 // 思路：采用二分查找的思路，优先搜索中间元素，判断其是否大于左右两边的元素，若是，直接返回该元素。 //否则，判断该元素与相邻元素的上升或下降趋势，若上升，保留右半边。若下降，保留左半边，继续重复上述过程， //直到元素数小于3停止递归调用 //关键词：单峰 二分 递归 优化少于 O(n) int siglePeak(int arr[],int left,int right) { int mid = left + (right- left)/2;//x + (y - x) / 2 if(arr[mid]> arr[mid-1]&& arr[mid]> arr[mid+1]) return arr[mid]; else{ if(arr[mid-1] < arr[mid]&& arr[mid-2]< arr[mid-1]) siglePeak(arr,mid+1,right); // 右边 else if(arr[mid] > arr[mid+1] && arr[mid +1] > arr[mid+2]){ siglePeak(arr,left,mid-1); } } } int main(){ int arr[] = { 1,3,5,8,9,7,6,1,2 }; cout<<siglePeak(arr,0,8); return 0; }运行效果如下图所示。
根据主定理可知，时间复杂度T(n)=T(n/2)+2，此时该算法复杂度为T(n)=O(logn)。
设A是一个n个不同元素的排好序的数组，给定数L和U，L<U，设计一个优于O(n)的算法，找到A中满足L<x<U的所有数x。
答：利用二分法查找L和U的位置，若找不到，则返回大于L的最小数位置，或小于U的最大数的位置。
代码：
// 二分法 查找插入位置 int searchInsert(int* Array, int left, int right, int target) { while (left <= right) { int mid = left + (right - left) / 2; if (Array[mid] == target) return mid; else if (Array[mid] < target)//如果中间值偏小，将初端右移 left = mid + 1; else //中间值偏大则终端左移 right = mid - 1; } return left;//如果目标值target比最大值还大，最后left>right，left=nums.size() //如果比最小值还小，最后left值为0，因为right会先减为-1后与left交换，left=0且比right大，跳出循环且符合题意，目标值变为初端 } void printL_U(int * arr,int L,int U,int length) { // length是数组长度 int i = searchInsert2(arr,1,length,L); int j = searchInsert2(arr,1,length,U); for (int m = i+1; m <j;m++) {// 输出i+1到j-1的数，因为L<x<U cout << arr[m]<<" , "; } } int main(){ int arr[] = { 1,1,2,3,5,7,8,9 }; printL_U(arr,1,7,8); // L=1，U=7 数组长度为8 return 0; }运行效果：
设A={a1,a2,…,an},B={b1,b2,…,bm}是整数集合，其中m=O(logn)，设计一个优于O(nm)的算法找出集合C=A∩B。
答：可以将长度较小的数组排序(由于m=O(logn)，可知m较小)，可选择复杂度较小的排序算法如归并排序，所需时间复杂度为O(mlogm)，再将每个B集合的每个元素作为Key，利用二分搜索去排好序的A数组中寻找，查找for循环运行n次，内部的二分搜索O(logm)，for循环关键操作O(nlogm)，总的时间复杂度T(n)= O(mlogm)+ O(nlogm)= O((m+n)logm)= O(nlogm)
#include <vector> #include <iostream> using namespace std; // 二分查找 void merge(int *arr,int low, int mid, int high) { //merge函数将两部分，（分别排好序的子数组），合并成一个，再存于原数组arr int h, i, j, k; h = low; i = low; j = mid + 1; // h,j作为游标，i指向temp存放数组元素的游标 vector<int> temp(5); // 这个temp数组是local的,长度为数组arr长度 while (h <= mid && j <= high) { // 当两个集合都没有取尽时 if (arr[h] <= arr[j]) { temp[i] = arr[h]; h = h + 1; } else { temp[i] = arr[j]; j++; } i++; } if (h > mid) { // 当第一子组元素被 取尽，而第二组元素未被取尽时 for (int k = j; k <= high; k++) { temp[i] = arr[k]; i++; } } else { // 当第2组取尽，第一组未被取尽时 for (int k = h; k <= mid; k++) { temp[i] = arr[k]; i++; } } for (int k = low; k <= high; k++) {//将临时数组temp中的元素再赋值给arr arr[k] = temp[k]; } } void mergeSort(int *arr,int low, int high) { // arr[low..high]是一个全程数组，含有high-low+1个待排序元素 if (low < high) { int mid = (low + high) / 2; mergeSort(arr,low, mid); mergeSort(arr,mid + 1, high); merge(arr,low, mid, high); } } int BinarySearch(int *a,int left, int right,int k)//k是要找的数字 { int m = left + (right - left) / 2; if (left > right)//查找完毕没有找到答案，返回-1 return -1; else { if (a[m] == k) return m;//找到!返回位置. else if (a[m] > k) return BinarySearch(a,left, m - 1,k);//找左边 else return BinarySearch(a,m + 1, right,k);//找右边 } } int main() { int a[] = { 1,5,4,7,8 }; int b[] = { 4,5,6,10,1,2,3,8,12 }; vector<int> c ; int count=0; mergeSort(a,0,4); //归并排序 O(nlogn) for (int i = 0; i < 9;i++) { int temp=BinarySearch(a, 0, 4, b[i]); if (temp != -1) { c.push_back(a[temp]); count++; } } for (int i = 0; i < c.size();i++) { cout << c[i]<<" , "; } return 0; }运行效果：
