ToB企服应用市场:ToB评测及商务社交产业平台

标题: 二分（折半查找）详细解答（边界条件终止条件等等详细解释） [打印本页]

作者: 盛世宏图 时间: 2023-12-14 07:15
标题: 二分（折半查找）详细解答（边界条件终止条件等等详细解释）
刷 Leetcode 总能遇到关于二分的题目，但是之前也只是草草地了解一下，每次在使用的时候都需要找模板，要不然就需要对于边界条件进行调试，着实是很麻烦！！！
二分介绍：

首先来简单介绍一下二分：二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求 线性表 必须采用 顺序存储结构，而且表中元素按关键字有序排列。
优点：

比较次数少：二分查找每次将搜索范围缩小一半，因此比较次数较少，查找速度快。
时间复杂度低：在有序数组中，二分查找的时间复杂度为O(log n)，其中n为搜索范围的大小。相比线性查找的O(n)时间复杂度，二分查找更高效。
可靠性高：由于二分查找是基于有序数组进行的，因此在数组有序的前提下，可以保证查找结果的准确性。

缺点：

要求有序数组：二分查找要求待查表为有序表，如果数组无序，则需要先进行排序操作，增加了额外的时间复杂度。
插入删除困难：由于二分查找是基于有序数组进行的，插入和删除操作会破坏数组的有序性，因此在插入和删除元素时需要维护数组的有序性，增加了操作的复杂度。

适用范围以及题型：　　在一段有序序列中寻找指定元素（或者该序列中不存在指定元素，返回小于等于指定元素的最大值）等等
二分法讲解：

arr数组为有序序列<br>left: 左边界
right:右边界
mid = (left + right) / 2: 中间下标
循环条件: left .. right<br>

复制代码

上述为二分中的左边界（left），右边界（right），中间元素下标（mid）.
二分法分类：
1.闭区间（左边界 left = 0, 右边界 right = arr.size() - 1）

先插入代码：
[code] // 1 2 3 5 6 8 9 10（有序数组中的元素） int left = 0, right = arr.size() - 1; int goal = 5;while(left arr[mid]){ left = mid + 1; }else{ right = mid - 1; } cout

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)