递推、递归、二分、贪心、倍增

二分法：

是一种在有序数组中查找特定元素的搜索算法。

前提是有序

搜索过程是从中间开始，如果中间值恰好是目标值，那么搜索结束。

如果目标大于或小于中间值，则在数组的大于或小于中间值的一半去找，减少寻找范围。

1～100

中间值 50 如果50大了 那么目标就是1～50

中间值 25 如果25小了 那么目标就在25～50

直到找到中间值

------------------------

#include <iostream>

using namespace std;

int main(){

   int n,x;

   cin>>n;

   for(int i=0;i<n;i++){

       cin>>a[i];

   }

   cin>>x;

   //假设当前有序，

   int l=a[0],r=a[n-1];

   while(l<r){

       int m=(l+r)/2;

       if(a[m]==x) {

           cout<<m;

           return 0;

       }

       else if(a[m]>x) r=m-1;

       else if(a[m]<x) l=m+1;

   }

   cout<<-1;

   return 0;

}

   1、初始化：找到数组的最小值和最大值

   int low=a[0],high=a[n-1];

   2、找中间值：

   int mid=(low+high)/2;

   3、比较：

       相等：找到了

       目标值较大：去掉一半

       目标值较小：去掉一半

   4、循环2-3步，直到相等

   5、如果找到了，输出答案，否则输出-1

二分法的时间复杂度：

最优情况：O(1),恰好在中间，一次就可以找到

平均和最坏情况：O(logn)，n指元素的数量

log16在c++里指2^?=16  ?=4  如果有16个数字，那么需要找4次可以找到

如果n=100需要多少次？2^6=64 <= 100 <= 2^7=128 所以找100个数字要7次

如果n=1000需要多少次？10次

基础算法：第七章分治算法的题