【每日一题C】#189. 实现折半查找

分手后的思念是犯贱 2023-10-11 17:31 10阅读 0赞

**题目描述：**

给定 N 个整数和 K个待查找的整数 M1,M2,…,Mk。如果待查找的整数在给定的 N 个整数中，请输出待查找的整数是数组中第几个元素（从 1 开始计算，第一个元素计 1 而不是0 ）；如果待查找的整数不在给定的 N 个整数中，则输出 0 。

**输入：**

测评机可能会反复运行程序，每次程序运行后，测评机输入包括三行。第一行输入两个整数N( 1≤N≤10^6 ）和 KK（1≤K≤10^6 ），分别表示给定的整数总个数和待查找的数的个数；第二行从小到大输入 N个整数 Numbersi（ 1≤Numbersi≤10^6，其中 1≤i≤N），每两个整数之间用一个空格隔开;第三行输入 K 个整数 Numbersj（ 1≤Numbersj≤10^66 ，其中 1≤j≤K），每两个整数之间用一个空格隔开。

**输出**

输出为一行，包括 K个部分，每个部分为题目描述中待查找的元素索引或 0 ，K 个部分之间用一个空格分隔。输出行尾不含多余空格。

思路：

可以利用二分法进行查找，查找的数组长度跟据n确定

代码：

#include<stdio.h>
    int fun(int *arr,int n,int x){
    	int head=0,tail=n-1,mid;
    	while(head<=tail){//二分查找
    		mid=(head+tail)/2;
    		if(arr[mid]==x)return mid+1;
    		else if(arr[mid]<x) head=mid+1;
    		else tail=mid-1;	
    	}
    	return 0;
    }
    int main(){
    	int n,k;
    	scanf("%d%d",&n,&k);
    	int arr[n];//变长数组
    	for(int i=0;i<n;i++){
    		scanf("%d",arr+i);
    	}
    	for(int i=0;i<k;i++){
    		int x;
    		scanf("%d",&x);
    		if(i) printf(" ");
    		printf("%d",fun(arr,n,x));
    	}
    	printf("\n");		   
    	return 0;
    }

输入输出示例：

5 2
    1 4 6 7 8
    5 1
    0 1