二分法：夹缝中求和

题目：https://ac.nowcoder.com/acm/contest/8997/D

import java.util.*;
public class Main{
    static int[] a;
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int x = in.nextInt();
        int y = in.nextInt();
        a = new int[n];
        for(int i = 0; i<n; i++){
            a[i] = in.nextInt();
        }
        Arrays.sort(a);
        long result = 0;
        for(int i=0; i<a.length - 2; i++){
            long min = binarySearchMin(i+1, a.length, x-a[i]);
            long max = binarySearchMax(i+1, a.length, y-a[i]);
            result += max - min;
        }
        System.out.println(result);
    }

    private static int binarySearchMin(int begin, int end, int num){
        int left = begin;
        int right = end - 1;
        int min = end;
        while(left <= right){
            int mid = (left + right) / 2;
            if(a[mid] >= num){
                min = mid;
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return min;
    }

    private static int binarySearchMax(int begin, int end, int num){
        int left = begin;
        int right = end - 1;
        int min = end;
        while(left <= right){
            int mid = (left + right) / 2;
            if(a[mid] > num){
                min = mid;
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return min;
    }
}

首先看标题就知道，二分法，数据结构没有好好听，所以呢，做起来就非常的苦难了。再次复习时，也一定要再次复习二分法的方法，借鉴别人的代码时发现，我们要找出下界和上界，在找出这两个之后，还要考虑，这两个数是否有重复的，难点就在这里，我们要利用二分法找出下界最左边的数，以及上界最右边的数，别人的经验非常丰富，以至于自己看了半天（废话少说）。别的代码不多做解释，因为要自己在回来看的时候要再多多理解一下代码。方法名（开始，结束，关键数），那么每次方法开始，开始和结束都是一样的，只有关键数，找下界的关键数是用x-a[i]，那么找上界的关键数是用y-a[i]，这样很巧妙，至于为什么，反正我只学会了 二分查找（进阶的）。

 private static int binarySearchMax(int begin, int end, int num){
        int left = begin;
        int right = end - 1;
        int min = end;
        while(left <= right){
            int mid = (left + right) / 2;
            if(a[mid] > num){
                min = mid;
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return min;
    }

二分查找（进阶）：
以：1 1 1 2 2 2 3 3 4 4 4 5 6 7 7为例
首先找下界时，数组左右分别为begin和end，那么关键数为num，例如num=1时，开始循环，mid = 0+14，mid=7，也就是3，在循环之后呢，会来到left=a[0],right=a[1]，那么这个时候mid=0，那么a[mid]就是最小最左边的数了。
寻找上界的时候，num=y-a[i]，num=3,那么mid=7，此时不是最右边的上界，那么就开始循环，不大于num则左边+1，但是呢mid还是7，继续+1，那么mid=8，a[mid]=4，那么就大于了3，此时继续循环就可以一直进行到结束，而right都不动。