顺序查找和二分查找
程序员文章站
2022-03-14 09:57:36
...
问题
写出两种检索算法:在一个排好序的数组T[1..n]中查找x,如果x在T中,输出x在
T的下标j;如果x不在T中,输出j=0.
解析
顺序查找过程:从表中的最后一个记录开始,逐个进行记录的关键字与给定值进行比较,若某个记录的关键字与给定值相等,则查找成功,找到所查的记录;反之,若直到第一个记录,其关键字和给定值比较都不相等,则表明表中没有所查的记录,查找失败。
二分查找,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功
设计
int f(int *a,int n,int m)
{
int i;
for (i=0;i<n;i++)
{
if (a[i]==m)
return 1;
}
return 0;
}
binarySearch(int a[], int n, int key){
int low = 0;
int high = n - 1;
while(low<= high){
int mid = (low + high)/2;
int midVal = a[mid];
if(midVal<key)
low = mid + 1;
else if(midVal>key)
high = mid - 1;
else
return mid;
}
return -1;
}
源码
#include <stdio.h>
int f(int *a,int n,int m)
{
int i;
for (i=0;i<n;i++)
{
if (a[i]==m)
return 1;
}
return 0;
}
int main()
{
int a[10]={1,2,3,4,5,6,7,8,9,10},c;
c=f(a,10,5);
if (c)
printf("找到");
else
printf("未找到");
return 0;
#include <stdio.h>
binarySearch(int a[], int n, int key){
int low = 0;
int high = n - 1;
while(low<= high){
int mid = (low + high)/2;
int midVal = a[mid];
if(midVal<key)
low = mid + 1;
else if(midVal>key)
high = mid - 1;
else
return mid;
}
return -1;
}
int main(){
int i, val, ret;
int a[8]={-32, 12, 16, 24, 36, 45, 59, 98};
for(i=0; i<8; i++)
printf("%d\t", a[i]);
printf("\n请输人所要查找的元素:");
scanf("%d",&val);
ret = binarySearch(a,8,val);
if(-1 == ret)
printf("查找失败 \n");
else
printf ("查找成功 \n");
return 0;
}
上一篇: 递归例题五:放苹果
下一篇: 【程序设计实习】之【魔兽世界3】