7-1 二分查找 (20分)

利用二分查找找出所给出的数在数组中的下标

输入格式:

第一行输入n和m表示数组有n个数据，m表示要对m个数进行查找

输出格式:

所有输出在一行完成，行末没有多余空格和多余回车。

输入样例:

5 5
1 2 3 4 5
1 2 3 4 5

输出样例:

0 1 2 3 4

 

作者: 陈英

单位: 南昌航空大学

时间限制: 50 ms

内存限制: 64 MB

代码长度限制: 16 KB

题目详情

 

时间限制50ms题目要求是二分查找，应该别的也用不了了，那就用二分查找吧~

数组给的是有序的

所以确定了low 和high，如果没有答案，就看 （low+high）/2

如果相等则跳出，不等则更新 low或high

#include<iostream>
#include<vector>
using namespace std;
int main(){
	int a,b,t;
	scanf("%d %d",&a,&b);
	vector<int> v(a);
	for(int i=0;i<a;i++)scanf("%d",&v[i]);
	int low=0;
	int high=a-1;
	for(int i=0;i<b;i++){
		scanf("%d",&t);
		 low=0;
		 high=a-1;
		 if(v[low]==t){
		 	high=low;
		 }else if(v[high]==t){
		 	low=high;
		 }
		 while(v[(low+high)/2]!=t){
		 	if(v[(low+high)/2]<t){
		 		low=(low+high)/2;
			 }else{
			 	high=(low+high)/2;
			 }
		 }
		 if(i!=0){
		 	printf(" ");
		 }
		printf("%d",(low+high)/2);
	}
	return 0;
}