普通的二分查找如下。要求给的数组有序。算法题里出现有序的情况时，用二分查找能将数组内查找的时间复杂度从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;
}
}
网友评论