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

二分法查找(C语言)

程序员文章站 2022-06-04 18:37:04
二分法是一种高效的查找方法,其适用于 已经排好序 的数组 基本思路 从数组最中间的数开始查找判断,若不是需要查找的数字,则比较大小,之后则在从中间分开的两边中的一边从最中间开始查找判断,以此类推 算法描述 这里以升序数组为例,降序数组类似 1. 记录数组最中间数的下标,将其中的数与要查找的数进行比较 ......

二分法是一种高效的查找方法,其适用于已经排好序的数组

基本思路

从数组最中间的数开始查找判断,若不是需要查找的数字,则比较大小,之后则在从中间分开的两边中的一边从最中间开始查找判断,以此类推

算法描述

这里以升序数组为例,降序数组类似

  1. 记录数组最中间数的下标,将其中的数与要查找的数进行比较
  2. 若相等,停止查找,若大于要查找的数,则将数组下标上限换为较大半区的最小下标;若小于要查找的数,则将数组下标的下限换为较小半区的最大下标
  3. 重复第一步,直到数组下标不能调换,若查找到则停止查找,若未找到,则返回不存在的结果

代码实现

这里以升序数组为例,降序数组类似

# include<stdio.h>
int f(int, int [], int);
int main()
{
    int n;
    int arr[10]={1,2,3,4,5,6,7,8,9,10};
    scanf("%d", &n);//输入要查找的数 
    int m=f(n, arr, 10-1);
    if(f(n, arr, 10-1)!=-1)
    printf("该数所在下标为:%d\n", m);
    else
    printf("该数不存在\n"); 
}
int f(int n, int a[], int h)
{
    int i, l, mid;
    l = 0;
    while(l<=h)//注意有等号,因为可能最后一次查找就只剩一个数,则这时上下限下标相等
    {
        mid=(l+h)/2;//计算中间下标
        if(a[mid]==n)//判断是否为目标数
        return mid;
        else if(a[mid]<n)
        l=mid+1;//如果中间数小于目标数,则将数组下限改为较大半区的下限
        else 
        h=mid-1;//如果中间数大于目标数,则将数组上限改为较小半区的上限
    }
    return -1;//返回-1表示目标数不存在
}