C语言入门教程
OutOfMemory.CN技术专栏-> C语言-> C语言入门教程-> C语言二分查找(折半查找)算法及代码

C语言二分查找(折半查找)算法及代码

二分找也称折半找,其优点是查找速度快,缺点是要求所要找的数据必须是有序序列。该算法的基本思想是将所要找的序列的中间位置的数据与所要找的元素进行比较,如果相等,则表示找成功,否则将以该位置为基准将所要找
二分找也称折半找,其优点是查找速度快,缺点是要求所要找的数据必须是有序序列。该算法的基本思想是将所要找的序列的中间位置的数据与所要找的元素进行比较,如果相等,则表示找成功,否则将以该位置为基准将所要找的序列分为左右两部分。接下来根据所要找序列的升降序规律及中间元素与所查找元素的大小关系,来选择所要找元素可能存在的那部分序列,对其采用同样的方法进行找,直至能够确定所要查找的元素是否存在,具体的使用方法可通过下面的代码具体了解。
#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;
}
运行结果:
-32    12    16    24    36    45    59    98
请输入所要查找的元素:12
查找成功
在上面的代码中,我们成功地通过二分找算法实现了查找功能,其实现过程如下图所示。


二分找算法的找过程

在如上图所示的查找过程中,先将序列中间位置的元素与所要找的元素进行比较,发现要找的元素位干该位置的左部分序列中。接下来将mid的左边一个元素作为 high,继续进行二分找,这时mid所对应的中间元素刚好是所要找的元素,找结束,返回找元素所对应的下标。在main函数中通过返回值来判断找是否成功,如果找成功.就打印输出“找成功”的信息,否则输出“找失畋”的信息。
© 内存溢出 OutOfMemory.CN