欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

顺序查找和二分查找

程序员文章站 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;
}