二分查找上下界

普通的二分查找如下。要求给的数组有序。算法题里出现有序的情况时，用二分查找能将数组内查找的时间复杂度从O(N)降到O(logn)。

    int bSearch(int[] array, int k){
        if(array == null || array.length==0) //判断异常值
            return -1;
        int l = 0, r = array.length-1, mid;
        while (l<=r){ //注意等号
            mid = l+((r-l)>>1); //写成 mid = l + (r-l)/2 也可以。这样可以防止l+r溢出。
            if(array[mid]>k)
                r=mid-1; 
            else if(array[mid]<k)
                l=mid+1;
            else
                return mid;
        }
        return -1;
    }

求上下界如下。对有些算法题来说很有用。
核心思想是，要求哪一个边界，另一个边界就要把=情况也考虑进入，从另一边界压缩左右间的空间。

int lowerBound(int[] array, int k){
        if(array == null || array.length==0)
            return -1;
        int l = 0, r = array.length-1, mid;
        while(l<=r){
            mid = l + ((r-l)>>1);
            if(array[mid]>=k)
                r = mid - 1;
            else
                l = mid + 1;
        }
        if(array[l] >= k)
            return l;
        else
            return -1;
    }

    int upperBound(int[] array, int k){
        if(array == null || array.length==0)
            return -1;
        int l = 0, r = array.length-1, mid;
        while(l<=r){
            mid = l + ((r-l)>>1);
            if(array[mid]<=k)
                l = mid + 1;
            else
                r = mid - 1;
        }
        if(array[r] <= k)
            return r;
        else
            return -1;
    }

例题：

今日头条算法题 用户喜好
时间限制：3秒
空间限制：262144K
为了不断优化推荐效果，今日头条每天要存储和处理海量数据。假设有这样一种场景：我们对用户按照它们的注册时间先后来标号，对于一类文章，每个用户都有不同的喜好值，我们会想知道某一段时间内注册的用户（标号相连的一批用户）中，有多少用户对这类文章喜好值为k。因为一些特殊的原因，不会出现一个查询的用户区间完全覆盖另一个查询的用户区间(不存在L1<=L2<=R2<=R1)。
输入描述:
输入： 第1行为n代表用户的个数 第2行为n个整数，第i个代表用户标号为i的用户对某类文章的喜好度 第3行为一个正整数q代表查询的组数 第4行到第（3+q）行，每行包含3个整数l,r,k代表一组查询，即标号为l<=i<=r的用户中对这类文章喜好值为k的用户的个数。 数据范围n <= 300000,q<=300000 k是整型
输出描述:
输出：一共q行，每行一个整数代表喜好值为k的用户的个数
输入例子1:
5
1 2 3 3 5
3
1 2 1
2 4 5
3 5 3

输出例子1:
1
0
2

例子说明1:
样例解释:
有5个用户，喜好值为分别为1、2、3、3、5，
第一组询问对于标号[1,2]的用户喜好值为1的用户的个数是1
第二组询问对于标号[2,4]的用户喜好值为5的用户的个数是0
第三组询问对于标号[3,5]的用户喜好值为3的用户的个数是2

解

直接顺序查找会说您的程序未能在规定时间内运行结束。
解法是记录对每个k来说，用户序号出现的位置。

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        HashMap<Integer, List<Integer>> like = new HashMap<>();
        int n = input.nextInt();
        int k;
        for(int i=1; i<=n; i++){
            k = input.nextInt();
            if(like.containsKey(k)){
                List<Integer> list = like.get(k);
                list.add(i);
            }
            else {
                List<Integer> list = new ArrayList<>();
                list.add(i);
                like.put(k, list);
            }
        }

        int q = input.nextInt();
        int l, r ,result = 0;
        for(int i = 0; i<q; i++){
            l=input.nextInt();
            r=input.nextInt();
            k=input.nextInt();
            result = 0;
            List<Integer> list = like.get(k);
            //这里其实用顺序查找也能ac，仅做演示。
            if(list!=null){
                Integer[] array = list.toArray(new Integer[0]);
                int start = lowerBound(array, k);
                int end = upperBound(array, k);
                if(start!=-1 && end !=-1)
                    result = end - start + 1;
            }
            System.out.println(result);
        }

    }
    static int lowerBound(Integer[] array, int k){
        if(array == null || array.length==0)
            return -1;
        int l = 0, r = array.length-1, mid;
        while(l<=r){
            mid = l + ((r-l)>>1);
            if(array[mid]>=k)
                r = mid - 1;
            else
                l = mid + 1;
        }
        if(array[l] >= k)
            return l;
        else
            return -1;
    }

    static int upperBound(Integer[] array, int k){
        if(array == null || array.length==0)
            return -1;
        int l = 0, r = array.length-1, mid;
        while(l<=r){
            mid = l + ((r-l)>>1);
            if(array[mid]<=k)
                l = mid + 1;
            else
                r = mid - 1;
        }
        if(array[r] <= k)
            return r;
        else
            return -1;
    }
}

转载于:https://www.jianshu.com/p/ed819f86ca5f