折半查找又称为二分查找。它仅适用于有序的顺序表。
折半查找的基本思想：首先给定值 key 与表中中间位置的元素比较，若相等，则查找成功，返回该元素的存储位置；若不等，则所需查找的元素只能在中间元素以外的前半部分或后半部分（例如，在查找表升序排列时，若给定值 key 大于中间元素，则所查找的元素只可能在后半部分）。然后在缩小的范围内继续进行同样的查找，如此重复，知道找到位置，或确定表中没有所需要查找的元素，则查找不成功，返回查找失败的信息。
算法：
typedef int ElemType; typedef struct MyStruct //查找表的数据结构（顺序表） { int TableLen ; //表的长度 ElemType* elem; //动态数组的基址 }SeqList; //折半查找 int Binary_Search(SeqList L, ElemType key) { int low = 0, high = L.TableLen - 1,mid; while (low<=high) { mid = (low + high) / 2; // 获取中间位置 if (L.elem[mid]==key) { return mid; // 查找成功则返回所在位置 } else if(L.elem[mid]>key) { high = mid - 1; //从前半部分继续查找 } else { low = mid + 1; //从后半部分继续查找 } } return -1; //查找失败，返回-1 }
算法解释
