考研数据结构考试中的考点——折半查找与折半插入排序

​ 前言

本文内容起源于王道老师的《数据结构（C语言版）》（第2版）讲解所获的学习心得笔记整理与总结。

插入排序的三种方法：直接插入排序、折半插入排序和希尔排序。

本文内容主要围绕 折半插入排序 以及其采用的 折半查找法 的理论基础及其典型实例分析展开讨论。该排序算法基于顺序表实现（使用C++编程语言）。

本文“干货”较足，建议收藏以防丢失。

可搭配以下链接一起学习：

考研

考研

考研复习：数据结构

考研阶段的学习重点：数据结构

本文已加入活动赛事：其链接为21天学习挑战赛

一、基本概念

1、折半插入排序( Binary Insertion Sort ) 的概念

采用 折半查找法 查找当前记录在已排好序的序列中的插入位置。

2、折半查找

1、又称二分查找， 仅适用于有序的顺序表 。不适用于数据元素经常变动的线性表。

2、算法思想

第一步是将键值key与表格中的中间单元格进行比较；如果相等，则匹配成功，并返回该元素的位置信息。

若两值不等，则该寻找的目标只能位于中间值之外的那一半；比如，在有序列表中（例如），当给定值key超过中间值时，则该寻找的目标只可能存在于后半个区间内；接着，在缩减后的区间内反复执行同样的搜索过程直至找到目标为止；当表中不存在所需元素时，则该