二分查找

二分查找的大体模板很简单，但是上课的时候看到结束条件下边界和上边界有时候相等有时候不等；mid有时候加一有时候不加一；本来感觉没什么太大的意义；后来问了百度才知道，细节是魔鬼！

二份查找的基本框架

int Search(int *num, int target) {
    int left = 0, right = ...;
    while(...) {
        int mid = (right + left) / 2;
        if (num[mid] == target) {
            ...
        } else if (num[mid] < target) {
            left = ...
        } else if (num[mid] > target) {
            right = ...
        }
    }
    return ...;

下面从两个方面细说

寻找一个数、寻找边界；

寻找一个数

问题大概是

搜索一个数，如果存在，返回其索引，否则返回 -1。

int Search(int*num, int target) {
    int left = 0; 
    int right = num.length - 1; //
    while(left <= right) { // 注意
        int mid = (right + left) / 2;
        if(num[mid] == target)
            return mid; 
        else if (num[mid] < target)
            left = mid + 1; // 注意
        else if (num[mid] > target)
            right = mid - 1; // 注意
        }
    return -1;
}

有两个值得注意的细节

1是结束条件 left <= right 因为我们right = num.length - 1;即r=最后一个元素当然前提是从num【0】开始输入的； left <= right 就是遍历的区间【l，r】是闭区间；

如果是 left < right就是开区间【l，r）；显然最后一个元素别遗漏了；但是如果我right = num.length；那么就代表开区间【l，r）r是最后一个元素再后一个；

这样子就可以把最后一个元素包括了

2 mid是否加一

本题因为 num[mid]有三种情况所以当num[mid]=目标的时候就输出了；也就是说num[mid]这个值已经被遍历了不用再继承了；

但是寻找边界的时候情况又不同；

寻找边界

左边界

int left(int*nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0;
    int right = nums.length; // 注意

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

需要注意的细节

1 while(left < right) 因为r是最后一个元素的下一个；所以用开区间就可以；

2 left = mid + 1，right = mid 因为我们的搜索区间是 [left, right) 左闭右开，所以当 nums[mid] 被遍历之后，下一步的搜索区间应该去掉 mid 分割成两个区间，即 [left, mid) 或 [mid + 1, right)。刚好把mid给去掉

if (nums[mid] == target)

right = mid;

意思是把上边界改成mid 因为 mid已经符合条件了但不一定是最左边的边界；所以这样从left到mid来遍历，看有没有其他边界；没有或者有都输出left 有统一性；因为有另一个边界的时候和没有循环结束的条件都是left=right；这样子就找到最左边的边界了

下面给出例题

是寻找边界的变例区间由整数集变成连续的小数集

HDU 1551 Cable master

将n根网线切成k段相同长度的网线，问可切成的最长长度是多少；

思路：利用二分发查找答案，每次偏右查找（因为要查找大的）也就是查找右边界；

sum = sum/k;
        double l = 0,r = sum;
        while(fabs(l-r)>exp)
        {
            double mid = (l+r)/2;
            if(judge(mid))
                l = mid+1;
            else
                r = mid;
        }
        printf("%.2f\n",l-1);
    }

    return 0;
}
int judge(double s)
{
    int cnt = 0;
    for(int i = 0; i<n; i++)
    {
        cnt+=(int)(a[i]/s);
    }
    if(cnt>=k) return 1;
    return 0;
}

1遍历区间是有小数的形式所以不能用大于或者大于等于的这种形式这样不够精确

2因为我们初始化 right = sum；

所以决定了我们的「搜索区间」是 [left, right)

所以决定了 while (left +10e-6< right)

同时也决定了 left = mid 和 right = mid

因为我们需找到 target 的最右侧索引

所以当 cnt== target 时不要立即返回

而要收左侧边界以锁定右侧边界

又因为收左侧边界时必须 left = mid 而不是left = mid+1；这是因为区间是连续的不是离散的整数；

3返回 left

返回right可能会出错可能恰好left+10e-6越界了；

细节决定ac！

2021-05-16二分查找

二分查找

寻找一个数

寻找边界