关于二分查找(折半查找)的记录

/ 算法 / 2 条评论 / 33浏览

关于二分查找(折半查找)的记录

之前其实也学习过二分查找的理念,但是一直有一个模糊的地方就是中间元素的选取。

二分查找需要的数组需要是有序的。

二分查找的步骤

  1. 确定数组的中间元素

  2. 将待查找元素与中间元素比较

  3. 如果大于中间元素,则到右边的数组查找,反之同理

  4. 如果中间元素等于待查找元素,那么查找成功。

之前一直迷惑的一点就是第一步当中的中间元素的选取,因为数组会有两种情况,一种是元素的个数为偶数,另一种是数组元素个数为奇数。

今天到网上查找相关资料,才补上了这个基础的知识:

中间元素的选取可以使用如下公式:mid = left + (right - left)/2;

这样不论当数组元素个数为偶数或者奇数的时候都可以正确选取到中间元素。

二分查找的思想

其实二分查找是利用的算法设计思想中的 分治法,一步一步缩小查找范围,最终得到问题的解。

分治法:将一个复杂的问题分解为多个相同或相似的子问题,再对子问题进行求解,进而得到问题的解。

二分法的求解过程可以用二叉树来描述,对于一个有序的数组,根结点为最开始选取的中间元素,根结点的左右两个孩子分别为左数组的中间节点及右数组的中间节点,孩子的孩子同理;

所以通过查找树(判定树)可以看出查找的元素要经过几次比较以及跟哪些元素进行了比较。

二分查找的时间复杂度

O(log2n)