二分查找

2021/7/10 6:06:03

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

整数二分

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

  • 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 }

 



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


扫一扫关注最新编程教程