基本算法篇——二分查找

技术分享 3年前 (2022-11-05) 0 999+

关注

基本算法篇——二分查找

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

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

二分查找简述

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

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

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

确定一个分界点

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

确定一个查找条件

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

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

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

二分查找模板

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

第一套模板

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

第二套模板

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);         }     } }