二分查找

本文主要是介绍二分查找，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

整数二分

整数二分要考虑边界问题，可以将二分查找分为两种情况。

• mid = (left + right) / 2

1 left = 0; right = n - 1;
2 mid = (left + right) / 2;
3 //查找x
4 while(left < right){
5     if(array[mid] >= x) //当前mid的值大于等于查找值，即此时查找结果在mid的左边（包括mid）——result <= mid
6         right = mid;
7     else //当前mid的值小于查找值，此时查找结果在mid的右边（不包括mid）
8         left = mid + 1;
9 }

• mid = (left + right + 1) /2

left = 0; right = n - 1;
mid = (left + right + 1) / 2;
while(left < right){
    if(array[mid] <= x) //当mid的值小于等于查找的值，此时结果在mid的右边，所以需要让left = mid.
        left = mid;
    else 
        right = mid - 1;
}

因为这里除法的取整是向下取整，所以当left = right - 1时，mid = (left + right) / 2 = left，这时循环中若left = mid则会造成死循环，所以需要在mid赋值时使其向上取整，这样不会造成死循环且不会影响最后的结果。

例题：数的范围

给定一个按照升序排列的长度为 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

输出样例：

3 4
5 5
-1 -1

 1 import java.io.BufferedInputStream;
 2 import java.util.Scanner;
 3 
 4 public class Main{
 5   public static void main(String[] args){
 6     Scanner scan = new Scanner(new BufferedInputStream(System.in));
 7     int n = scan.nextInt();
 8     int m = scan.nextInt();
 9     int[] q = new int[n];
10     for(int i = 0; i < n; i++) q[i] = scan.nextInt(); 
11     while(m > 0){
12       int l = 0, r = n - 1; // l 与 r的定义需要在第一个while中，因为每次m值改变则代表一次查找的结束，需要重新定义一次l与r，若放在循环外会影响第一次以外的查找
13       int x = scan.nextInt();
14       while(l < r){
15         int mid = (l + r) / 2;
16         if(q[mid] >= x) r = mid;
17         else l = mid + 1;
18       }
19       if(q[l] != x) System.out.println("-1 -1");
20       else{ //若已查找到第一个索引位置，则再进行一次查找
21         System.out.print(l + " ");
22         l = 0; r = n - 1;
23         while(l < r){
24           int mid = (l + r + 1) / 2;
25           if(q[mid] <= x) l = mid;
26           else r = mid - 1;
27         }
28         System.out.println(l);
29       }
30       m--;
31     }
32   }
33 }

浮点数二分

浮点数二分比较简单，因为不需要考虑边界问题，直接取mid即可。

1 left = 0; right = n - 1;
2 while(l < r){
3     double mid = (l + r) / 2;
4     if(check(mid)) r = mid;
5     else l = mid;
6 }

这篇关于二分查找的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！