二分查找

• 引入
  试想这么一个场景：你在翻阅花名册（按照字母顺序排列）中寻找一位姓氏首字母为P的同学的名字时，是会从花名册的第一行开始寻找，还是会从花名册大约中间部位开始寻找？
  相信所有人都会选择后者的方法，因为这种方法的时间复杂度会低很多，其实这就运用了二分查找的思想。

• 正文
  再次分析一下上文引入的例子，具体化我们要做的事：首先从中间将花名册分为两部分，比较要找的对象和分割处的名字。如果分割处的名字就是要找的对象，那么寻找过程结束。如果名字在分割点的前面，那么对前面那一部分再进行寻找，反之则反。

• 核心代码

  int name_find(int q){
  int l=1,r=n+1;//根据实际情况判定范围区间
  while(l<=r){ //这里是判定条件，要根据实际情况进行调整
    int mid=l+(r-1)/2; //避免数据溢出，当然如果确定不会溢出也可以直接用算数平均值
    if(a[mid]>=q) r=mid+1; //同理需要根据实际情况判定
    else l=mid+1;
    }
  if(a[l]==q) return l;
  else return -1;
  }