C语言折半查找法详解与代码实现

核心逻辑与使用前提

折半查找法仅适用于对已经有序的数组或数据进行操作，通常默认为从小到大排列。其本质是通过不断调整范围边界（即改变 low 和 high 的下标值），将中间位置 mid 锁定在目标 key 所在处。因此，mid 的计算公式 mid=(high+low)/2 必须放置在循环内部，且循环条件为 high >= low。在此过程中，low、mid 和 high 均表示下标。

不同排序方向的判断差异

根据原始数据的排列方式，比较 key 与 mid 指向元素的大小关系时，区间收缩的方向会有所不同：

情况一：数据由小到大排列（升序）

当待查值小于中间值时，说明目标位于左半边，右边界 high 需左移至 mid-1；反之则位于右半边，左边界 low 右移至 mid+1。

      mid=(high+low)/2;
      if(key<a[mid])//说明要找的值在左边
        high=mid-1;
      else if(key>a[mid])//说明要找的值在mid右边
        low=mid+1;//最小值的位置往右进一位

情况二：数据由大到小排列（降序）

若数据为降序排列，比较逻辑恰好相反：key 大于中间值时目标在左侧（high=mid-1），key 小于中间值时目标在右侧（low=mid+1）。

mid=(high+low)/2;
if(key>a[mid])//注意是由大到小排列 ，所以此时key在a【mid】 左边，故high=mid-1 ；
  high=mid-1;
else if(key<a[mid])//注意是由大到小排列，所以此时key在a【mid】右边，故low=mid+1；
  low=mid+1;

完整代码实现

为了确保折半查找法的正确运行，必须在调用前保证数据已排好序。以下代码提供了一个封装好的查找函数，支持输入自定义长度、生成数组并执行查找。如果需要在非排序数组上使用，可在其中嵌入冒泡排序或选择排序作为预处理步骤。

以下是基于升序数据的完整 C 语言实现，包含计数器以展示查找效率：

#include<stdio.h>
void zb(int key,int a[],int n) //key表示要找的数，a表示数组，n表示数组元素个数 
{
    int i,high,low,mid;
    int count1=0,count=0; //count记录查找次数，count1标记是否找到
    low=0;
    high=n-1;
    while(high>=low)//保证右下标不小于左下标 
    {    
       count++;
       mid=(high+low)/2; //mid应处于循环里面，每次迭代重新计算中间位置
        if(key<a[mid])//说明key在a【mid】的左半边 ,那么最右边的high下标就可以在下标mid基础上往左进一个单位了
       high=mid-1;
        else if(key>a[mid])//说明key在a【mid】的右半边 ,那么最左边的low下标就可以在下标mid基础上往右进一个单位了 
        low=mid+1;
       if(key==a[mid])
       {
           printf("元素找到了！！！\n一共查找了%d次\n它处于a[%d]位置上\na[%d]=%d\n",count,mid,mid,key);
           count1++;
           break;
       }
   }
    if(count1==0)
   printf("元素不存在！！！\n");
}
int main ()
{
    int key,n,a[100];
    int i;
    void zb(int key,int a[],int n); //声明函数
    printf("请输入数组元素个数：\n");
    scanf("%d",&n);
    printf("请输入（从小到大）所有数组元素：\n");
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    printf("请输入要查找的数：\n");
    scanf("%d",&key);
    zb(key,a,n);
    printf("\n");
    return 0;
}