数据结构-有序表的折半查找 （C语言代码）

解题思路:设置折半查找函数即可。

注意事项:注意有重复元素时，返回第一次出现的位置。

参考代码:

#include <stdio.h>
int search(int a[],int n,int x)  //返回数组a中第一个大于或等于被查找数据x的位置 
{
	int left,right,mid;
	left=0; right=n-1;
	while(left<=right)
	{
		mid=(left+right)/2;
		if(x>a[mid])
			left=mid+1;
		else
			right=mid-1;
	}
	return left; 
}
int main()
{
	int a[1005],b[1005];
	int n,k,pos,x;
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++)
		scanf("%d",&a[i]);
	for(int i=0;i<k; i++)
		scanf("%d",&b[i]);
	for(int i=0;i<k; i++)
	{
		x=b[i];
		pos=search(a,n,x);
		printf("%d ",a[pos]==x?pos:-1);
	} 
	printf("\n");
	return 0;
}

也可以不写search函数，程序如下：

#include <stdio.h>
int main()
{
	int a[1005],b[1005];	
	int n,k,x;
	int left,right,m;
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++)
		scanf("%d",&a[i]);
	for(int i=0;i<k;i++)
		scanf("%d",&b[i]);
	for(int i=0;i<k;i++) 
	{
		x=b[i];
		left=0; 
		right=n-1;
		while(left<=right)
		{
			int m=(left+right)/2;
			if(x>a[m])
				left=m+1;
			else
				right=m-1;
		}
		printf("%d ",a[left]==x?left:-1);
	}
	printf("\n");
	return 0;
}

或者直接用C++的STL函数：lower_bound（）,该函数的功能：返回数组中第一个大于或等于被查找数据的位置 
，具体用法看程序。

#include <bits/stdc++.h> 
using namespace std;
int main()
{
	int a[1005],b[1005];
	int n,k,pos,x;
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++)
		scanf("%d",&a[i]);
	for(int i=0;i<k; i++)
		scanf("%d",&b[i]);
	for(int i=0;i<k; i++)
	{
		x=b[i];
		pos=lower_bound(a,a+n,x)-a; //返回数组中第一个大于或等于被查找数据的位置 
		printf("%d ",a[pos]==x?pos:-1);
	} 
	printf("\n");
	return 0;
}