二分法查找是一个经典的算法:二分查找又叫折半查找
1. 作用和要求
当我们要从一个序列中查找一个元素的时候,二分查找是一种非常快速的查找算法,二分查找又叫折半查找。它对要查找的序列有两个要求,一是该序列必须是有序的(即该序列中的所有元素都是按照大小关系排好序的,升序和降序都可以,本文假设是升序排列的),二是该序列必须是顺序存储的。图1展示的就是一个能进行二分查找的序列。
图1 有序且顺序存储的序列
如果一个序列是无序的或者是链表,那么该序列就不能进行二分查找。之所以被查找的序列要满足这样的条件,是由二分查找算法的原理决定的。
2. 算法原理
二分查找算法的原理如下:
1. 如果待查序列为空,那么就返回-1,并退出算法;这表示查找不到目标元素。
2. 如果待查序列不为空,则将它的中间元素与要查找的目标元素进行匹配,看它们是否相等。
3. 如果相等,则返回该中间元素的索引,并退出算法;此时就查找成功了。
4. 如果不相等,就再比较这两个元素的大小。
5. 如果该中间元素大于目标元素,那么就将当前序列的前半部分作为新的待查序列;这是因为后半部分的所有元素都大于目标元素,它们全都被排除了。
6. 如果该中间元素小于目标元素,那么就将当前序列的后半部分作为新的待查序列;这是因为前半部分的所有元素都小于目标元素,它们全都被排除了。
7. 在新的待查序列上重新开始第1步的工作。
二分查找之所以快速,是因为它在匹配不成功的时候,每次都能排除剩余元素中一半的元素。因此可能包含目标元素的有效范围就收缩得很快,而不像顺序查找那样,每次仅能排除一个元素。
3. 示例
我们用两个示例来演示二分查找的过程,一看就能明白。第一个示例演示查找成功的情况,第二个示例演示查找不到目标元素的情况。
演示过程中用到的变量如下:low指向待查序列中的第一个元素,high指向待查序列中的最后一个元素,mid指向待查序列的中间元素,target代表要查找的目标元素。
3.1 查找成功的情况
假设原始序列为array=[3, 12, 24, 31, 46, 48, 52, 66, 69, 79, 82],目标元素target=52。
1. 开始时,low=0,high=10,mid=(low high) / 2 = 5。
比较中间元素和目标元素,48小于52。这说明若目标元素存在,则它必定在原序列的后半部分。让low=mid 1 = 6而high不变,这样low和high就指向了原序列的后半部分。
2. 此时,low=6,high=10,mid=(low high) / 2 = 8。
同样的,比较新的中间元素和目标元素,69大于52。这说明若目标元素存在,它必定在当前待查序列的前半部分。让high=mid - 1 = 7而low不变,这样low和high就指向当前待查序列的前半部分。
3. 此时,low=6,high=7,mid=(low high) / 2 = 6。
比较新的中间元素和目标元素,52等于52。查找成功,返回该中间元素的索引6并退出算法。
3.2 查找不到的情况
假设原始序列为array=[5, 10, 22, 29, 43, 57, 58, 61, 73, 77, 81],目标元素target=70。
1. 开始时,low=0,high=10,mid=(low high) / 2 = 5;
比较中间元素和目标元素,57小于70。这说明若目标元素存在,那么它一定在原序列的后半部分。让low=mid 1 = 6而high不变,这样low和high就指向原序列的后半部分。
2. 此时,low=6,high=10,mid=(low high) / 2 = 8;
比较新的中间元素和目标元素,73大于70。这说明若目标元素存在,那么它一定在当前待查序列的前半部分。让high=mid - 1 = 7而low不变,这样low和high就指向当前待查序列的前半部分。
3. 此时,low=6,high=7,mid=(low high) / 2 = 6;
比较新的中间元素和目标元素,58小于70。这说明若目标元素存在,那么它一定在当前待查序列的后半部分。让low=mid 1 = 7而high不变,这样low和high就指向当前待查序列的后半部分。
4. 此时,low=7,high=7,mid=(low high) / 2 = 7;
比较新的中间元素和目标元素,61小于70。这说明若目标元素存在,那么它一定在当前待查序列的后半部分。让low=mid 1 = 8而high不变。
5. 此时,low=8,high=7,low大于high说明待查序列已为空,也就说明查找不到目标元素。此时,返回-1并退出算法,表示查找不成功。
4. 算法实现
我们给出二分查找的一个简单的实现,其它情况可以依此类推。在该简单实现中,我们使用C语言并且假设序列中的元素是整数。
/* * Function: binarySearch * Description: 二分查找的实现,如果查找成功则返回目标元素在序列中的索引; 如果查找不成功则返回-1. * Param: array 待查序列 * Param: n 序列中的元素个数 * Param: target 要查找的目标元素 * Return: 目标元素在序列中的索引或-1 */int binarySearch(int array[], int n, int target) { /* * 定义并初始化low和high,声明mid */ int low = 0; int high = n - 1; int mid; /* * 如果low小于或等于high,则说明待查序列不为空; * 需要将其中间元素和目标元素进行匹配。 */ while (low <= high) { /* 计算中间元素的索引 */ mid = (low high) / 2; if (array[mid] == target) { /* 查找成功,返回该中间元素的索引 */ return mid; } else if (array[mid] > target) { high = mid - 1; } else { /* array[mid] < target */ low = mid 1; } } /* 没有匹配的元素 */ return -1;}
5. 二分查找的性能分析
5.1 时间复杂度
在最好的情况下只需要进行1次比较就能找到目标元素,那么最坏的情况呢?此时,可以借助该序列的二叉树形式进行分析。将一个序列转换为二叉树的过程是这样的:将它的中间元素作为它的根节点,将中间元素之前的前半部分作为它的左子树,将中间元素之后的后半部分作为它的右子树;在创建左子树和右子树的时候递归利用这一规则。
比如第3.2小节的序列[5, 10, 22, 29, 43, 57, 58, 61, 73, 77, 81]可以构建成如图2所示的二叉树。
图2 序列的二叉树形式
5.2 空间复杂度
在我们的实现中,二分查找对于存储空间的要求是只需要能存储low、high、mid、target、数组地址(参数array)和数组元素数量(参数n)这6个局部变量就行了,因此它对存储空间的要求是常数数量,不随着元素多少而变化。所以它的空间复杂度为O(1)。
(完)
- 01-07显微成像教程 泡菜说,如何搭建简易显微摄影系统
- 04-062023考研调剂一览表:考研B区院校调剂信息汇总
- 10-04物流运输会计账务处理全套,物流运输行业会计分录大全
- 03-14重生夺宝转盘:寻宝抽奖奇迹重生唯一快速成型的途径
- 01-24dunk腰果花春夏秋冬都可以穿吗?腰果花dunk秋天首选腰果花
- 11-27十大建议买的固态硬盘品牌 国际一线大品牌固态硬盘
- 01-29澳洲留学和英国留学哪个性价比高?出国留学花费,二
- 04-25蜂王有哪些特点和作用?蜂王毒腺发达却从来不会蜇人
- 12-06喀尔喀蒙古族服饰特点:肃南草原上的一抹靓丽风情
- 12-22郑少秋为啥喜欢官晶华 郑少秋人人喊打的渣男
- 04-07乡村便民服务站运营方案 天门已建成543个村级综合便民服务站
- 12-27vim取消临时显示文件的行号:这通惊为天人的操作没sei了
- 10-27森林进化论森林之战第二站 豆瓣9.2,森林进化论综艺独树一帜的成功之路
- 02-02云鹿智能门有几款 云鹿智能门凭什么这么贵
- 12-20岁月静好因为有你唯美的句子:经典语录愿春天早点到来
- 04-19龙珠超次元乱战剧场版大结局:龙珠,超次元乱战集合
热门
推荐
- 1未来十大热门行业有哪些381
- 2中秋散文大全469
- 3网络经济的市场营销论文165
- 4详细简历模板131
- 5负荆请罪成语典故249
- 6社区两学一做动员会讲话稿329
- 7父母怎么才能提高孩子的应变能力269
- 8怎样介绍三峡景点216