折半查找，也称二分查找，在某些情况下相比于顺序查找，使用折半查找算法的效率更高。但是该算法的使用的前提是静态查找表中的数据必须是有序的。
例如，在{5,21,13,19,37,75,56,64,88 ,80,92}这个查找表使用折半查找算法查找数据之前，需要首先对该表中的数据按照所查的关键字进行排序：{5,13,19,21,37,56,64,75,80,88,92}。
在折半查找之前对查找表按照所查的关键字进行排序的意思是：若查找表中存储的数据元素含有多个关键字时，使用哪种关键字做折半查找，就需要提前以该关键字对所有数据进行排序。
在这边，我使用了三种语言来实现：
一、C语言实现二分查找
#include <stdio.h> #include <stdlib.h> #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; }
二、PHP实现二分查找
// 非递归 // $target是要查找的目标 $arr是已经排序好的数组 function binary(&$arr,$low,$top,$target){ while($low <= $top){ //由于php取商是有小数的，所以向下取整，不过也可不加，数组也会取整 $mid = floor(($low+$top)/2); if($arr[$mid]==$target){ return $mid; }elseif($arr[$mid]<$target){ $low = $mid+1; }else{ $top = $mid-1; } } return -1; } $arr = array(1,3,6,9,13,18,19,29,38,47,51,56,58,59,60,63,65,69,70,71,73,75,76,77,79,89); echo binary($arr, 0, sizeof($arr), 9); // 递归 function binaryRecursive(&$arr,$low,$top,$target){ if($low<=$top){ $mid = floor(($low+$top)/2); if($arr[$mid]==$target){ return $mid; }elseif($arr[$mid]<$target){ return binaryRecursive($arr,$mid+1,$top,$target); }else{ return binaryRecursive($arr,$low,$mid-1,$target); } }else{ return -1; } } $arr = array(1,3,6,9,13,18,19,29,38,47,51,56,58,59,60,63,65,69,70,71,73,75,76,77,79,89); echo binaryRecursive($arr, 0, sizeof($arr), 9); //
三、python实现二分查找
def binarySearch(arr, l, r, x): # 基本判断 if r >= l: mid = int(l + (r - l) / 2) # 元素整好的中间位置 if arr[mid] == x: return mid # 元素小于中间位置的元素，只需要再比较左边的元素 elif arr[mid] > x: return binarySearch(arr, l, mid - 1, x) # 元素大于中间位置的元素，只需要再比较右边的元素 else: return binarySearch(arr, mid + 1, r, x) else: # 不存在 return -1 # 测试数组 arr = [2, 3, 4, 10, 40] x = 10 # 函数调用 result = binarySearch(arr, 0, len(arr) - 1, x) if result != -1: print("元素在数组中的索引为 %d" % result) else: print("元素不在数组中")