二分(折半查找)详细解答(边界条件终止条件等等详细解释)

刷 Leetcode 总能遇到关于二分的题目,但是之前也只是草草地了解一下,每次在使用的时候都需要找模板,要不然就需要对于边界条件进行调试,着实是很麻烦!!!


二分介绍:

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

优点:

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

缺点:

  1. 要求有序数组:二分查找要求待查表为有序表,如果数组无序,则需要先进行排序操作,增加了额外的时间复杂度。
  2. 插入删除困难:由于二分查找是基于有序数组进行的,插入和删除操作会破坏数组的有序性,因此在插入和删除元素时需要维护数组的有序性,增加了操作的复杂度。
适用范围以及题型:

  在一段有序序列中寻找指定元素(或者该序列中不存在指定元素,返回小于等于指定元素的最大值)等等


二分法讲解:

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

上述为二分中的左边界(left),右边界(right),中间元素下标(mid).

二分法分类:

1.闭区间(左边界 left = 0, 右边界 right = arr.size() - 1)

先插入代码:

        // 1 2 3 5 6 8 9 10(有序数组中的元素)
        int left = 0, right = arr.size() - 1;
        int goal = 5;while(left <= right){
            int mid = ( left + right) / 2;
            if(goal > arr[mid]){
                left = mid + 1;
            }else{
                right = mid - 1;
            } 
            cout << "Left:" << left << "  " << "Right:" << right << "     " ;
        }     
        cout << "结果是" << left << endl; 

我们直接进行分析(先不要想为什么这样子,先跟着我的思路走):
(1)闭区间初始化:
  left = 0, right = arr.size() - 1,则此时 left 和 right 代表的分别是数组序列的起始元素和末尾元素
(2)循环条件的设置:
  循环结束的标志是区间内没有元素,因此只有当 left < right 的时候才会终止,因此设置 while(left <= right)
(3)循环中 if 语句满足与不满足后的 left 和 right 的设置
  暂时不讨论为什么这样子设置

来看终止情况:
终止前的一次: left == right
设 X = left, Y = right (这里的X和Y是不会变的,因为此时 left == right,所以可以 X == Y)
此时 mid == X (或者Y),结果只有两种可能,goal对应元素下标为 (1)X对应的  或者 (2)X + 1对应的
    前面这句话不理解可以看 while 循环中的 if 语句,流程图如下:

 

接着我们分析两种情况:
情况一:X对应的元素是目标值
  则此时进入 if 语句,判断为 N,进入第二个执行语句: right = mid - 1, 则此时 left 不变,结果就是 left, 就是 X

情况二:X + 1对应的元素是目标值
  则此时进入 if 语句,判断为 Y,进入第一个执行语句:left = mid + 1,则此时结果仍然是 left, 就是 X + 1

综上:cout << l << endl; 就可以得到正确答案!


  

 

 



热门相关:试婚老公,要给力   余生皆是喜欢你   试婚老公,要给力   覆汉   绍宋