c语言编程实现“折半查找”的过程。

//参考代码如下：

#include <stdio.h>

int main()

{

int i, j, n, k=0, isFound=0

int num[15] = {88,86,75,74,61,56,52,43,39,34,31,22,18,16,8} //测试数组

printf("请输出一个整数：\n")

scanf("%d", &n)

i = (int)15/2 //对折位移量

j = (int)15/2 //取数“指针”

while(k<2)

{

i = (int)i/2

if(i == 0) k++//i==0 即折半到无可再折时，仍有最后一次比较，故以k做计数

//若未相等，计算下一循环指针的位置

if(n<num[j])

j = j + (i + 1)

else if(n>num[j])

j = j - (i + 1)

else

{

isFound = 1

break //若找到相等数，标记已找到并退出循环

}

}

//输出结果

if(isFound)

printf("该数是数组中第%d个元素的值\n", j)

else

printf("查无此数！\n")

return 0

}

折半查找法是算法一种，可以被任何计算机语言使用。用C语言自然也可以实现。

1、定义：

在计算机科学中，折半搜索（英语：half-interval search），也称二分搜索（英语：binary search）、对数搜索（英语：logarithmic search），是一种在有序数组中查找某一特定元素的搜索算法。

搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

2、查找规则：

折半查找法是效率较高的一种查找方法。假设有已经按照从小到大的顺序排列好的五个整数a0~a4，要查找的数是X，其基本思想是： 设查找数据的范围下限为l=0，上限为h=4，求中点m=（l+h）/2，用X与中点元素am比较，若X等于am，即找到，停止查找；否则，若X大于am，替换下限l=m+1，到下半段继续查找；若X小于am，换上限h=m-1，到上半段继续查找；如此重复前面的过程直到找到或者l>h为止。如果l>h，说明没有此数，打印找不到信息，程序结束。

3、C语言参考代码：

int bin_search(int A[],int n,int key){

//在长度为n的数组A 中折半查找值为key的元素，并返回下标值。如果不存在则返回-1.

    int low,high,mid

    low = 0

    high = n-1//初始low和high为数组的两端。

    while(low<=high)

    {

        mid =(low + high)/2//查找中心点。

        if(A[mid]==key)return mid//已找到，返回下标值。

        if(A[mid]<key){//中点位置比key值小，以mid+1为新的下限值。

            low =mid + 1

        }

        if(A[mid]>key){//中点位置比key值大，以mid-1为新的上限值。

            high= mid - 1

        }

    }

    return -1//未找到，返回-1.

}

#include<stdio.h>

int main()

{int a[16]={15,14,13,12,11,10,9,8,7,6,5,4,3,1,0}

 int l=0,r=15,mid,x

 scanf("%d",&x)

 do

 {mid=(l+r)/2

  if(a[mid]==x)break

  if(x>a[mid])r=mid-1

    else l=mid+1

 }while(l<=r)

 if(a[mid]==x)

   printf("a[%d]=%d\n",mid,x)

 else

   printf("无此数\n")  

 return 0    

}

---