二分法查找 | 您所在的位置:网站首页 › 算法二分法查找 › 二分法查找 |
1、二分查找(Binary Search) 二分查找又称折半查找,它是一种效率较高的查找方法。 二分查找要求:线性表是有序表,即表中结点按关键字有序,并且要用向量作为表的存储结构。不妨设有序表是递增有序的。 2、二分查找的基本思想 二分查找的基本思想是:(设R[low..high]是当前的查找区间) (1)首先确定该区间的中点位置: (2)然后将待查的K值与R[mid].key比较:若相等,则查找成功并返回此位置,否则须确定新的查找区间,继续二分查找,具体方法如下: ①若R[mid].key>K,则由表的有序性可知R[mid..n].keys均大于K,因此若表中存在关键字等于K的结点,则该结点必定是在位置mid左边的子表R[1..mid-1]中,故新的查找区间是左子表R[1..mid-1]。 ②类似地,若R[mid].keyhigh时表示查找区间为空,查找失败 } //BinSeareh 二分查找算法亦很容易给出其递归程序【参见练习】 4、 二分查找算法的执行过程 设算法的输入实例中有序的关键字序列为 (05,13,19,21,37,56,64,75,80,88,92)要查找的关键字K分别是21和85。具体查找过程【参见动画演示】 5、二分查找判定树 二分查找过程可用二叉树来描述:把当前查找区间的中间位置上的结点作为根,左子表和右子表中的结点分别作为根的左子树和右子树。由此得到的二叉树,称为描述二分查找的判定树(Decision Tree)或比较树(Comparison Tree)。 注意: 判定树的形态只与表结点个数n相关,而与输入实例中R[1..n].keys的取值无关。 【例】具有11个结点的有序表可用下图所示的判定树来表示。
(1)二分查找判定树的组成 ①圆结点即树中的内部结点。树中圆结点内的数字表示该结点在有序表中的位置。 ②外部结点:圆结点中的所有空指针均用一个虚拟的方形结点来取代,即外部结点。 ③树中某结点i与其左(右)孩子连接的左(右)分支上的标记""、")"表示:当待查关键字 KR[i].key)时,应走左(右)分支到达i的左(右)孩子,将该孩子的关键字进一步和K比较。若相等,则查找 过程结束返回,否则继续将K与树中更下一层的结点比较。 (2)二分查找判定树的查找 二分查找就是将给定值K与二分查找判定树的根结点的关键字进行比较。若相等,成功。否则若小于根结点的关键字,到左子树中查找。若大于根结点的关键字,则到右子树中查找。 【例】对于有11个结点的表,若查找的结点是表中第6个结点,则只需进行一次比较;若查找的结点是表中第3或第9个结点,则需进行二次比较;找第1,4,7,10个结点需要比较三次;找到第2,5,8,11个结点需要比较四次。 由此可见,成功的二分查找过程恰好是走了一条从判定树的根到被查结点的路径,经历比较的关键字次数恰为该结点在树中的层数。若查找失败,则其比较过程是经历了一条从判定树根到某个外部结点的路径,所需的关键字比较次数是该路径上内部结点的总数。 【例】待查表的关键字序列为:(05,13,19,21,37,56,64,75,80,88,92),若要查找K=85的记录,所经过的内部结点为6、9、10,最后到达方形结点"9-10",其比较次数为3。 实际上方形结点中"i-i+1"的含意为被查找值K是介于R[i].key和R[i+1].key之间的,即R[i].key= left;j-- )// 后移排序码大于R[i]的记录 array[j+1] = array[j]; array[left] = num;// 插入 }} int rcmp( const int *a, const int *b){ return (*a-*b);}void main() { int array[50]; int i; printf("The original array is :\n"); for( i=0; i |
CopyRight 2018-2019 实验室设备网 版权所有 |