一般为分:顺序和折半(又叫二分)查找两种方法。
存放在数组中的数据就可以看成一堆数据,在有限数组内存放一些数据,通过使用查找方法进行查找想要找的数。
顺序方法:这种查找方法不需要数组排序,数据可以是无序的。从数组开头向后一个一个与被查找数进行比较,如果找到就做相应的操作(如输出这个数的下标或位置)等。
折半查找法:(二分查找)
前提需要把数组里的数据进行排序(升序或降序)。思路是(假设数组已按升序排序)每次只比较中间的数据(一段距离内),第一次先和中间的数组(下标是这个数组中在中间的)比较,如果相同,则说明被找数已找到。否则就要判断是在大于还是小于:如果是大于,那么就将在中间+1至最后一个数之间的中间数再进行比较。否则就将在第一个至中间-1的数进行比较;再次重复比较,直到找到数为止。
从题目的叙述来看,这个函数的功能就是这一个包含有len个元素的num数组中查找是否存在值为key的元素。可以在找到后返回该元素的下标,否则返回-1。这个函数的函数体可以这么写:
int i
for(i=0i<leni++)
if(num[i]==key)return i
return -1
然后在主函数中的查找语句可以这么写:
if(searchNum(key,num,len)!=-1)
printf("找到!\n")
#define IntSize sizeof(int)#define StructSize sizeof(struct tagresult)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef int *ptint
typedef struct tagresult
{
int v
char bl
}*ptresult
int lessthan(const void *v1,const void *v2)
{
int i1=*((ptint)v1),i2=*((ptint)v2)
if(i1==i2)
return 0
else if(i1<i2)
return 1
else
return -1
}
int main()
{
int c,n,capacity=128,rlen=0,dlen
ptint data=(ptint)calloc(capacity,IntSize)
ptresult result
scanf("%d",&n)
result=(ptresult)calloc(n,StructSize)
memset(result,0,n*StructSize)
while(n-->0)
{
scanf("%d",&c)
dlen=0
for(c>0c--)
{
if(dlen+1>=capacity)
{
capacity*=2
data=(ptint)realloc(data,capacity)
}
scanf("%d",data+dlen++)
}
scanf("%d",&c)
//直接调用库函数qsort进行快速排序,就不自己写快速排序算法函数了
qsort(data,dlen,IntSize,lessthan)
if(c<=dlen)
{
(*(result+rlen)).v=*(data+c-1)
(*(result+rlen)).bl=1
}
rlen++
}
for(n=0n<rlenn++)
{
if(1==(*(result+n)).bl)
printf("Case #%d:%d\n",n+1,(*(result+n)).v)
else
printf("Case #%d:-1\n",n+1)
}
free(data)
free(result)
return 0
}