折半查找 折半查找（Binary Search），又称二分查找，适用于有序表的查找。 基本思想 将要查找的关键字与查找表的中间元素进行比较： 若相等则返回中间位置 若查找关键字比中间位置关键字小，则对前半部分递归 若查找关键字比中间位置关键字大，则对后半部分递归 前提条件 查找表必须是有序的（已按关键字排序） 采用顺序存储结构 算法分析 时间复杂度：O(log n) 每次比较排除一半的数据，效率远高于顺序查找 链接到 上一个知识点：4.3 顺序查找 下一个知识点：4.5 分块查找
