当日2023/1/12学习了二分查找,下面我会展示当日笔记:

二分查找

二分答案

基础

使用这个算法必须要是一个有序的序列

最好手写

给每个元素下标; 2. 设定left、mid、right的初始值;

3. 向左、向右、中间,缩小范围; 看清题目是不是第一次出现的位置!!! 不然用map做!!! 或者看以下操作!!!

中点成立,

分界点是中点或中点左侧

中点不成立,

分界点在中点右边

这种方法最后的结果是left;

模板

while (left < right)

         {

             mid = (left + right) >> 1;//中点公式,上取整,第一次成立的位置

             if (op <= a[mid])

                  right = mid;

             else

                  left = mid + 1;

         }//当无解时,left=n

 

 

         while (left < right)

         {

             mid = (left + right +  1) >> 1;//中点公式,下取整,最后一次成立的位置

             if (x >= a[mid])

                  right = mid;

             else

                  left = mid + 1;

         }//当无解时,left=0

相关题目见P2249.cpp

应用

在题目中,通过题目中给定的过程与mid比较,进行确定范围.

先要找到两个关系:

1. 不成立到成立——使用模板1;
2. 成立到不成立——使用模板2.

与普通的不同在于,在循环中多了个计算题目给定的计算过程.

下期有机会我将介绍system,HANDLE与CMD,Bye~