【算法训练】二分查找

二分查找

二分查找建立在待查找元素有序的前提上

例题
题目描述

输入N个学生的学号，然后查询输入
输入的第一行为N，即学生的个数(N<=1000)
接下来的N行包括N个学生的信息，信息格式如下：
01 李江 男 21
02 刘唐 男 23
03 张军 男 19
04 王娜 女 19
然后输入一个 M(M<=10000),接下来会有 M 行，代表 M 次查询，每行输入 一个学号，格式如下：
02
03
01
04

输出：

输出M行，，每行包括一个对应于查询的学生的信息。
如果没有对应的学生信息，则输出“No Answer!”

样例输入

4
01 李江 男 21
02 刘唐 男 23
03 张军 男 19
04 王娜 女 19
5
02
03
01
04
03

样例输出：

02 刘唐 男 23
03 张军 男 19
01 李江 男 21
04 王娜 女 19
03 张军 男 19

考虑到时间复杂度，采用二分查找

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
struct Student{
   char no[100];//学号
   char name[100];//姓名
   char sex[5];//性别
   int age; //年龄
   bool operator < (const Student &A) const{
       //重定向小于运算符
       return strcmp(no,A.no); 
   } 
}buf[1000];
int main(){
   int n;
   while(scanf("%d",&n)!=EOF){
       for(int i=0;i<n;i++){
           scanf("%s%s%s%d",buf[i].no,buf[i].name,buf[i].sex,&buf[i].age);
       }
       int m;
       scanf("%d",&m);
       while(m-- !=0){
           int ans=-1;//目标元素下标初始化为-1
           char x[30];
           scanf("%s",x);//输入待查学号
           int top=n-1,base=0;//初始化，开始下标为0，结束下标为n-1，查找子集为整个数组
           while(top>=base){
               int mid=(top+base)/2;//计算中间点的下标
               int tmp=strcmp(buf[mid].no,x);//比较中间点学号是否与目标学号相同
               if(tmp==0){
                   ans=mid;
                   break;
               } 
               else if(tmp>0){
                   top=mid-1;
               }else{
                   base=mid+1;
               }
           } 
           if(ans==-1){
               printf("NO Answer!\n");
           }else{
               printf("%s %s %s %d\n",buf[ans].no,buf[ans].name,buf[ans].sex,buf[ans].age);
           }
       }
   }
   return 0;
}

除了查找某特定元素是否存在以为，二分查找还有另一类非常重要的作用，即定界。
例如，在一个升序的数组中，确定一个下标点，使在这个下标点之前（包括该下标点）的数字均小于等于目标数字。

//存在一个升序的有序数组buf，其大小为size，目标数字为target
   int base =0,top=size-1;
   while(base<=top){
       if(top<=target) break;
       int mid=(base+top)/2;
       if(buf[mid]<=target) base=mid+1;
       else top=mid-1;
   } 
   int ans=top;