Acwing-基础算法课笔记之基础算法（二分）

一、二分查找的概念

1、使用二分的条件

1、必须是数组（顺序表）
2、必须有序

2、二分查找的算法流程

目标数：27

5	16	20	27	30	36	44	55	60	67	71
1	2	3	4	5	6	7	8	9	10	11

第一步：
需要定义两个变量，一个left，一个right，分别指向下标1和最后一个元素的下标11，确定查找的范围。

第二步：
取中间位置：mid=(left+right)/2，即mid=(1+11)/2=6

然后将27与mid下标所在的数做比较，如果27<a[mid]，则将指针right更新，如果27>a[mid]，则将指针left更新，最终找到目标数。

二、左闭右闭写法[left,right]

while(left <= right) {
mid = (left + right) / 2;
if(num[mid] > target)
right = mid - 1;
else if(num[mid] < target)
left = mid + 1;
else return mid;
}

三、左闭右开写法[left,right)

[1,1)

while(left < right) {
mid = (left + right) / 2;
if(num[mid] > target)
right = mid;
else if(num[mid] < target)
left = mid + 1;
else return mid;
}

四、浮点数的二分

bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

原文地址：https://blog.csdn.net/weixin_73381974/article/details/145268576

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！