基本算法篇——二分查找

本次我们介绍基础算法中的二分查找，我们会从下面几个角度来介绍二分查找：

• 二分查找简述
• 二分查找模板
• 二分查找边界
• 例题数的范围

二分查找简述

首先我们来简单介绍一下二分查找：

• 二分查找就是在一个数组中快速得找到我们所需要的值

• 二分查找通常是在有单调性的数组中进行；有单调性的数组必定可以二分，但二分可以运行在没有单调数的数组中

然后我们来介绍二查找分的思想：

1. 确定一个分界点

// 同样我们需要先确定一个分界点
// 我们的二分查找的分界点通常设计为(l+r)/2或者(l+r+1)/2，至于为什么+1我们后面讲解

1. 确定一个查找条件

// 我们需要给出一个你查找数所满足的条件
// 我们需要确定数组的一侧不满足这个条件，但另一侧满足这个条件
// 这时我们就只需要查找这个我们需要的数，使其一侧不满足条件，而另一侧满足条件

1. 更换边界值，不断进行递归查找

// 我们采用一种check算法来检查mid值是否满足条件，然后根据是否满足条件来判断我们所需要查找的值在哪一侧
// 然后我们更换边界值，不断进行运算，直到l==r时，这时会锁定一个数，而这个数就是我们所需要的数

二分查找模板

我们在实际使用中的二分查找模板只有两套，我们在下面给出：

1. 第一套模板

int bsearch_1(int l,int r){
    
    // 区间[l,r]划分为[l,mid]和[mid+1,r]使用
    
    // 首先对整个数组进行遍历
    while(l < r){
        
        // 约定一个起始的分界点
        int mid = (l+r)/2;
        
        // 对该分界点进行判定
        if(check(mid)){
            // 如果满足条件时该点在[l,mid]之间
            r = mid;
        } else {
            // 如果不满足条件时该点在[mid+1,r]之间
            l = mid + 1;
        }
        
    }
    
    // 最后我们l==r，这个点就是我们二分查找出来的点
    return l;
}

1. 第二套模板

int bsearch_1(int l,int r){
    
    // 区间[l,r]划分为[l,mid - 1]和[mid,r]使用
    
    // 首先对整个数组进行遍历
    while(l < r){
        
        // 约定一个起始的分界点
        int mid = (l+r+1)/2;
        
        // 对该分界点进行判定
        if(check(mid)){
            // 如果满足条件时该点在[mid,r]之间
            l = mid;
        } else {
            // 如果不满足条件，说明该点在[l,mid - 1]之间
            r = mid - 1;
        }
        
    }
    
    // 最后我们l==r，这个点就是我们二分查找出来的点
    return l;
}

二分查找边界

我们现在来介绍一下二分查找边界问题，也就是为什么+1：

int bsearch_1(int l,int r){
    
    // 区间[l,r]划分为[l,mid - 1]和[mid,r]使用
    
    // 首先对整个数组进行遍历
    while(l < r){
        
        // 约定一个起始的分界点
        int mid = (l+r+1)/2;
        
        // 对该分界点进行判定
        if(check(mid)){
            // 如果满足条件时该点在[mid,r]之间
            l = mid;
        } else {
            // 如果不满足条件，说明该点在[l,mid - 1]之间
            r = mid - 1;
        }
        
    }
    
    // 最后我们l==r，这个点就是我们二分查找出来的点
    return l;
}

/*
上述是+1的模板，我们+1的根本原因是因为边界问题，

因为我们将边界设置为l=mid，所以我们才需要对mid的赋值进行+1操作

因为我们的int类型是向下整分的，也就是2.5会变为2

那么如果我们的l = r - 1，这种情况下，我们的将l = mid = （l + l + 1）/2，这时l不会发生变化，我们的范围还是[l,r]不改变

因此为了避免无限循环，所以我们需要将mid的值加上0.5(1)，这时我们再将l = mid，l就会向前进1，这时就不会发生循环
*/

例题数的范围

• 我们给定一个数组，按顺序排列，我们需要得知其中某些数的起始位置和终止位置，若无该数返回-1 -1；

代码展示：

import java.util.Scanner;

public class Postion {
    public static void main(String[] args) {

        // 输入框
        Scanner scanner = new Scanner(System.in);

        // 数组长度
        int n = scanner.nextInt();

        // 查找个数
        int k = scanner.nextInt();

        // 数组内容
        int[] arr = new int[n];

        for (int i = 0; i < arr.length; i++) {
            arr[i] = scanner.nextInt();
        }

        // 开始循环
        while (k-- > 0){

            // 设置查找值
            int x = scanner.nextInt();

            // 边界设置
            int l = 0,r = n-1;

            // 开始二分查找
            while (l < r){
                // 先找左边界
                int mid = (l+r)/2;
                if (arr[mid] >= x){
                    r = mid;
                }else {
                    l = mid + 1;
                }

            }

            // 判定是否有这个数
            if (arr[l] != x){
                // 如果没有k返回return
                System.out.println("-1,-1");
            }else {
                // 如果有k，先打印左边界，我们再找右边界；(注意：此时r=l)
                System.out.println(l + " ");

                l = 0;
                r = n-1;

                while (l < r){
					// 查找右边界
                    int mid = (l+r+1)/2;
                    if (arr[mid] <= x){
                        l = mid;
                    }else {
                        r = mid - 1;
                    }
                }
            }
            // 打印右边界(注意：此时r=l)
            System.out.println(l);
        }
    }
}

好的，关于基础算法篇的二分查找就介绍到这里，希望能为你带来帮助~