基本算法篇——二分查找

基本算法篇——二分查找

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

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

二分查找简述

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

  • 二分查找就是在一个数组中快速得找到我们所需要的值
  • 二分查找通常是在有单调性的数组中进行;有单调性的数组必定可以二分,但二分可以运行在没有单调数的数组中

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

  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 
  1. 第二套模板
int bsearch_1(int l,int r){

    // 区间[l,r]划分为[l,mid - 1]和[mid,r]使用

    // 首先对整个数组进行遍历
    while(l 

二分查找边界

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

int bsearch_1(int l,int r){

    // 区间[l,r]划分为[l,mid - 1]和[mid,r]使用

    // 首先对整个数组进行遍历
    while(l 

例题数的范围

例题:

  • 我们给定一个数组,按顺序排列,我们需要得知其中某些数的起始位置和终止位置,若无该数返回-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  0){

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

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

            // 开始二分查找
            while (l = 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 

结束语

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

文章来源于互联网:基本算法篇——二分查找

THE END
分享
二维码