数据结构|数据结构——二分查找（折半查找）算法详解（C语言）算法|c语言|数据结构

折半查找，也称二分查找，在某些情况下相比于顺序查找，使用折半查找算法的效率更高。但是该算法的使用的前提是静态查找表中的数据必须是有序的。
也就是说，在使用折半查找算法查找数据之前，应该首先把该表的数据按照所查的关键字进行排序
折半查找算法对静态表查找表｛2，5，7，17，23，25，31，35，42，76，88｝采用折半查找算法查找关键字为17的关键字的过程为：

文章图片

如上图所示，指针 low 和 high 分别指向查找表的第一个关键字和最后一个关键字，指针 mid 指向处于 low 和 high 指针中间位置的关键字。在查找的过程中每次都同 mid 指向的关键字进行比较，由于整个表中的数据是有序的，因此在比较之后就可以知道要查找的关键字的大致位置。

例如在查找关键字 17 时，首先同 25 作比较，由于17< 25，而且这个查找表是按照升序进行排序的，所以可以判定如果静态查找表中有 17这个关键字，就一定存在于 low 和 mid 指向的区域中间。

因此，再次遍历时需要更新 high 指针和 mid 指针的位置，令 high 指针移动到 mid 指针的左侧一个位置上，同时令 mid 重新指向 low 指针和 high 指针的中间位置。如下图所示

文章图片

同样，用 17 同 mid 指针指向的 7作比较，7 < 17，所以可以判定 17 如果存在，肯定处于 mid 和 high 指向的区域中。所以令 low 指向 mid 右侧一个位置上，同时更新 mid 的位置。

文章图片

当第三次做判断时，发现 mid 就是关键字 17，查找结束
注意：在做查找的过程中，如果 low 指针和 high 指针的中间位置在计算时位于两个关键字中间，即求得 mid 的位置不是整数，需要统一做取整操作。
折半查找的实现代码：

#include #include #define keyType int typedef struct { keyType key; //查找表中每个数据元素的值 //如果需要，还可以添加其他属性 }ElemType; typedef struct{ ElemType *elem; //存放查找表中数据元素的数组 int length; //记录查找表中数据的总数量 }SSTable; //创建查找表 void Create(SSTable **st,int length){ (*st)=(SSTable*)malloc(sizeof(SSTable)); (*st)->length=length; (*st)->elem = (ElemType*)malloc((length+1)*sizeof(ElemType)); printf("输入表中的数据元素：\n"); //根据查找表中数据元素的总长度，在存储时，从数组下标为 1 的空间开始存储数据 for (int i=1; i<=length; i++) { scanf("%d",&((*st)->elem[i].key)); } } //折半查找算法 int Search_Bin(SSTable *ST,keyType key){ int low=1; //初始状态 low 指针指向第一个关键字 int high=ST->length; //high 指向最后一个关键字 int mid; while (low<=high) { mid=(low+high)/2; //int 本身为整形，所以，mid 每次为取整的整数 if (ST->elem[mid].key==key)//如果 mid 指向的同要查找的相等，返回 mid 所指向的位置 { return mid; }else if(ST->elem[mid].key>key)//如果mid指向的关键字较大，则更新 high 指针的位置 { high=mid-1; } //反之，则更新 low 指针的位置 else{ low=mid+1; } } return 0; } int main(int argc, const char * argv[]) { SSTable *st; Create(&st, 11); getchar(); printf("请输入查找数据的关键字：\n"); int key; scanf("%d",&key); int location=Search_Bin(st, key); //如果返回值为 0，则证明查找表中未查到 key 值， if (location==0) { printf("查找表中无该元素"); }else{ printf("数据在查找表中的位置为：%d",location); } return 0; }

运行结果为：