二分与前缀和_前缀 边界条件

知识点讲解：

实数二分，必然是一个确定的值。整数二分有一个向下取整的问题。

边界条件：设置一个长度，当R-L>1e-6 循环进行，否则退出

二分经典代码：
例题1：数的范围
给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。

对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。

如果数组中不存在该元素，则返回 -1 -1。

输入格式：
第一行包含整数 n 和 q，表示数组长度和询问个数。

第二行包含 n 个整数（均在 1∼10000 范围内），表示完整数组。

接下来 q 行，每行包含一个整数 k，表示一个询问元素。
输出格式：
共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。

如果数组中不存在该元素，则返回 -1 -1。

数据范围
1≤n≤100000
1≤q≤10000
1≤k≤10000

输入样例：

6 3
1 2 2 3 3 4
3
4
5
1
2
3
4
5

输出样例：

3 4
5 5
-1 -1
1
2
3

代码设计：

/**
 * 二分求解模板题
 * 
 */ 
import java.util.*;
public class Main{
    
    public static void main(String[]args){
        
        Scanner scan=new Scanner(System.in);
        
        int n=scan.nextInt();
        int q=scan.nextInt();
        int []array=new int[100001];
        for(int i=0;i<n;i++)
            array[i]=scan.nextInt();
       
        for(int i=0;i<q;i++){
             int l=0;
             int r=n-1;
            int x=scan.nextInt();
            while(l<r){//左半边
                
                int mid=(l+r)/2;
                
                if(array[mid]>=x)
                    r=mid;//r=mid 不需要加1
                else l=mid+1;
                
                
            }
            if(array[l]==x)//右半边
                {
                     System.out.print(l+" ");
                     r=n-1;
                     while(l<r){
                         int mid=(l+r+1)/2;
                         
                         if(array[mid]<=x)
                            l=mid;//l=mid 需要加1 防止死循环
                        else r=mid-1;
                         
                     }
                    System.out.println(l+" ");
                   }
            else System.out.println("-1 -1");
        }
        
    }
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51