二分查找与二分答案-java实现

翻洛谷的时候发现好多例题都做过，但谁让我过了两年啥都记不得了呢，只能复(预)习一下了（笑

二分查找

二分查找是一种利用二分的思想快速在有序数列里查找指定数位置的方法。

当然这个题要求用C的unsigned int而java没有这种东西，所以过不了。不过算法还是可以写一下的。

public static void main(String[] args){
        int n,m;
        Integer[] a  = new Integer[1000005];
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for(int i = 1;i<=n;i++){
            a[i]=sc.nextInt();
        }
        for(int i = 1;i<=m;i++){
            int target = sc.nextInt();
            int l = 1;int r = n;
            while(r-l>1){
                int mid = (l+r)/2;
                if(target <= a[mid]){
                    r = mid;
                }else{
                    l = mid;
                }
            }
            int ans;
            if(a[l]==target) ans = l;
            else if(a[r]==target) ans = r;
            else ans = -1;
            System.out.print(ans +" ");

        }
    }

主要思路：因为本人比较笨，所以就用笨方法来判断，不取巧。每次查询时定义左边界、有边界和mid，反复利用二分的方法找到中间值和目标值进行对比。因为数列有序，如果mid大于目标值，则在mid左边寻找，即把右边界改为mid，反之亦然。直到左边界和右边界靠在一起或重合（r-l<=1）时停止。

这个时候由于缩小边界时我们包含了边界，所以答案一定在边界上，要么是左边界要么是右边界，简单判断输出答案即可。

要注意的是数列中可能有很多重复的目标元素，所以为了取第一次出现的那个，遇见 a[mid] == target 时也要缩右边界，即把已经发现的这个target作为右边界。这样可以避免前面还有重复的元素，也不怕最后找不到答案，反正最后边界也是会被判断到的。

二分答案

二分答案是二分查找的一种更广泛的推广。

应用场景：求使某条件最大的某变量的最小可能情况/使某条件最小的某变量的最大可能情况

一般来说，使用二分答案要满足下列前提：

答案在固定区间内
很难直接搜索或遍历得到，但给出一个值可以很快判定它是否符合要求
查找区间具有有序性

例题

[P2678 NOIP2015 提高组] 跳石头 - 洛谷 | 计算机科学教育新生态

这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 N块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。
为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 M 块岩石（不能移走起点和终点的岩石）。
求最短跳跃距离的最大值。

和上面的三个前提对应：

答案在1-赛道长度之间，是固定区间；
可以使用较简单的方法判断某最短距离是否可行（下文说明）；
我们的答案范围最短跳跃距离为1-赛道长度，自然是有序的。

综上，可以使用二分答案解这道题。

为什么采用二分的思想？

设某种情况的最短跳跃距离为x、赛道长度为L，若最短跳跃距离为x可行，则[1, x)上的结果一定可行，但一定不为最优，所以答案一定在[x, L]上。反之，如果x不可行，则答案一定在[1, x)上。

这个过程和之前的二分查找不能说长得很像，只能说完全一致。所以采用二分思想来处理这个问题。

为什么说判断某最短距离是否可行满足“比较简单”的要求？

可以采用以下方法判断最短距离m是否可行：

按最短间隔m为标准移走石头，间隔<m的通通移走，记下移走的数目。如果移走的石头数目在输入给的上限以内，则m可行，否则不可行。

这种纯模拟的方式非常简单直观，相比于爆搜石头的具体移动方案，判断某个m是否可行要简单太多了。要想到这一点就是本题最大的难度。接下来就修改上面的二分查找即可。

代码实现

动代码，本题的关键在judge()函数，返回bool值，用于判断某个m值是否可行。

一开始我写了这个玩意：

static boolean judge(long m1){
        int count = 0;
        for(int i = 2;i<=n;i++){
            if(a[i]-a[i-1]<m1) count++;
        }
        if(count>m) return false;
        else return true;
    }

最后洛谷挂了7个点emmm

原因是为了满足m的最小间隙，不仅仅要移除一个石头。有可能要移除很多石头才能满足要求。用模拟的方法，模拟一个人慢慢跳，用while循环到结束为止。

新的judge方法：

static boolean judge(long m1){
        int count = 0;
        int i = 1;
        int now = 0;
        while(i<n+1){
            if(a[i]-a[now]<m1){
                count++;
            }else{
                now = i;
            }
            i++;
        }

        if(count>m) return false;
        else return true;
    }

至于主函数，把二分查找的代码简单拿出来做一个修改就好了。

成功AC~

完整代码：

import java.util.Scanner;

class Main {
    static long[] a  = new long[50005];
    static int len,n,m;
    static boolean judge(long m1){
        int count = 0;
        int i = 1;
        int now = 0;
        while(i<n+1){
            if(a[i]-a[now]<m1){
                count++;
            }else{
                now = i;
            }
            i++;
        }

        if(count>m) return false;
        else return true;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        len = sc.nextInt();
        n = sc.nextInt();
        m = sc.nextInt();
        for(int i = 1;i<=n;i++){
            a[i]=sc.nextInt();
        }
        long r = len, l = 1;
        while(r-l>1){
                long mid = (l+r)/2;
                if(!judge(mid)){
                    r = mid;
                }else{
                    l = mid;
                }
            }
        long ans;
        if(judge(r)) ans = r;
        else if(judge(l)) ans = l;
        else ans = -1;
        System.out.print(ans);
    }
}

总结而言，二分答案其实就是用二分的方式猜答案的一个过程，只是说有序数列需要抽象出来比较困难，同时也需要想到一个简单可行的judge()方法判断猜测的数据是否满足题意。

上一页【集训整理】最近公共祖先LCA 模板题下一页动态规划-java语言练习一：暴力DP

最后更新于1年前