二分查找详解（Java版）

server/2024/9/30 0:13:20/

 

目录

一.什么是二分查找？

二.二分查找的实现：

三.二分查找的进阶算法：

1.寻找左侧重复元素的索引值：

2.寻找元素有序排列的插入位置：

目的：

实现：

 举例：

细节：

3.左闭右开区间的二分查找处理：

理解：

细节：

总结：

一.什么是二分查找？

二分查找算法是一种高效的搜索算法，适用于 有序数组。它通过将查找范围不断减半，逐步缩小目标值的搜索空间，最终找到目标元素或确认目标不存在。

二分查找是解决有序数组查找问题的高效算法。

原理：

  • 用 while 循环不断调整搜索范围，直到找到目标值或搜索范围为空。
  • 从数组的中间元素开始比较：
    • 如果中间元素是目标值，搜索结束。
    • 如果目标值小于中间元素，则搜索范围缩小到数组的左半部分。
    • 如果目标值大于中间元素，则搜索范围缩小到数组的右半部分。
  • 重复上述步骤，直到找到目标值或搜索范围缩小到零。

时间复杂度：

  • O(log n)，因为每次都将搜索范围缩小了一半。

适用条件：

  • 数据必须是有序的。
  • 只适合静态数组，即在搜索过程中数组不会发生变化。

二.二分查找的实现：

按照上面的原理叙述，首先保证有序数组，不断利用循环算出左右两边界索引值的中间索引值，然后与目标值进行比较大小以此来不断压缩，最终找到目标值。

左闭右闭区间的细节：

  1. i <= j，因为是左闭右闭区间，需要保证边界索引值查找的数能查到的，有效的，所以需要在 i = j 的情况查找一次来判断目标值。
  2. int mid = (i + j) >>> 1，在计算两个边界索引值的中间索引值需要使用 Java 的 >>> 无符号右移运算符（高位补0，不考虑符号位），是为了避免在某些情况下当 i 和 j 都很大时，加法超出 int 的表示范围导致溢出。
  3. if 语句判断尽量全写 < 以此来满足正常的数组遍历思维。
  4. 找不到目标值需要返回 -1 来确认。
//O(log n)
//向下取整
public class BinarySearchOne {//全写小于号以便于与数组查找思维一致public static int binarySearch(int[] arr, int key) {int i = 0, j = arr.length - 1;//左闭右闭while (i <= j) { //i与j重合也要继续查一次int mid = (i + j) >>> 1;  // int mid = (i + j) / 2  使用>>>1(无符号右移)是为了防止超出正整数表示范围导致结果为负if(arr[mid] < key){i = mid + 1;}else if(key < arr[mid]){j = mid - 1;}else{return mid;}}return -1;}//mainpublic static void main(String[] args) {int[] a = {1,2,3,4,5,6,7,8,9,10};System.out.println(binarySearch(a, 10)); //输出：9}
}

三.二分查找的进阶算法：

对于二分查找，有很多的特例情况需要通过不同场景来分析加以使用。 

1.寻找左侧重复元素的索引值：

我们在上面最初的二分查找的基础上加以改进，设置第三变量 candidate 来记录最左侧重复索引值的位置，为了让找不到目标值的情况返回 -1 所以 candidate 的初始值设置为 -1，如果当 arr[mid] = target 的情况下出现，使用 candidate 来记录当前位置值，然后缩小 j 的边界位置，最后当 i > j 跳出循环返回 candicate 的值就可以找到最左侧重复元素索引值了。

public class BinarySearchLeftMost {//遇到重复元素找到最左侧的元素索引public static int binarySearchLeftMost(int[] arr,int target) {int i = 0, j = arr.length - 1;int candidate = -1;//如果找不到就会返回-1结果while(i <= j){int mid = (i + j) >>> 1;// int mid = (i + j) / 2  使用>>>1(无符号右移)是为了防止超出正整数表示范围导致结果为负if(arr[mid] < target){i = mid + 1;}else if(target < arr[mid]){j = mid - 1;}else{candidate = mid;//使用第三方变量记录当前找到的元素位置j = mid - 1;//继续查找是否还有最左侧的重复元素}}return candidate;}public static void main(String[] args) {int[] arr = {1,2,3,4,5,6,7,7,7,7,8,9};System.out.println(binarySearchLeftMost(arr,7));//输出6}
}

2.寻找元素有序排列的插入位置：

上面我们讲述了在最左侧寻找重复元素的索引值，但是如果找不到目标值，结果会返回 -1，如果我们想要实现寻找到元素有序排列的插入位置，我们可以在上面的寻找左侧重复元素的索引值的基础上进行改动，让其找不到目标值返回当前可以插入的位置。

目的：

在 有序数组 中查找一个元素 target，并返回它的 最左侧位置。如果数组中存在重复的 target，它会返回最左侧那个元素的索引。如果没有找到 target，则返回 target 应该插入的位置，这个位置可以被视为 target 在数组中的排名。

实现：

  • if (target <= arr[mid])：如果 target 小于等于中间元素 arr[mid]，那么我们要缩小搜索范围到数组的左侧，因为我们想找到最左边的那个元素（即便 target 和 arr[mid] 相等，我们也要继续往左找）。所以更新右边界 j = mid - 1。（这个部分也就是上面的部分代码的合并）
  • else：如果 target 大于 arr[mid]，说明目标元素只可能在数组的右侧，所以更新左边界 i = mid + 1。

 举例：

假设数组是 arr = [1, 3, 5, 7]，target = 4（找不到）：

  • 第一次 mid = 1，arr[mid] = 3，target > arr[mid]，所以 i = mid + 1 = 2。
  • 第二次 mid = 2，arr[mid] = 5，target <= arr[mid]，所以 j = mid - 1 = 1。
  • 循环结束，返回 i = 2，表示 4 不存在数组中，但可以插入到索引 2 的位置。

细节：

注意使用左边界记录位置并返回，因为当 i = j 的情况出现， j 是在此基础上做减法来向前推进边界索引值，而 i 是不在改变原本位置。

public class BinarySearchLeftPlus {//遇到重复元素找到最左侧的元素索引,找不到的情况下可以获得当前target所在排名public static int binarySearchLeftMost(int[] arr,int target) {int i = 0, j = arr.length - 1;while(i <= j){int mid = (i + j) >>> 1;// int mid = (i + j) / 2  使用>>>1(无符号右移)是为了避免在某些情况下当 i 和 j 都很大时，加法超出 int 的表示范围导致溢出。if(target <= arr[mid]){j = mid - 1;}else{i = mid + 1;}}return i;}public static void main(String[] args) {int[] arr = {1,2,3,4,6,7,7,7,7,8,9};System.out.println(binarySearchLeftMost(arr,7));//输出5System.out.println(binarySearchLeftMost(arr,10));//输出11System.out.println(binarySearchLeftMost(arr,5));//输出4}
}

3.左闭右开区间的二分查找处理：

理解：

我们可以将这种区间理解成因为 j 是开区间的边界，以至于不可以将这个边界的索引值作为有效值去参与比较，所以我们如果要是出现 i = j 这种情况会陷入死循环，并且当 target < arr[mid] 这种情况出现的时候，不可以让 j = mid - 1，这样会漏掉 mid - 1 索引位置的元素。

细节：

  1. i < j，因为j是不参与比较，如果要是i=j这种情况发生会陷入死循环。
  2. j = mid，如果是 mid - 1 会导致因为右侧开区间计算 mid 后 mid - 1 会漏掉 mid - 1 这个索引元素，因为j指向的索引元素不参与比较
public class BinarySearchRightOpen {//左闭右开查找区间段内的元素public static int binarySearch(int[] arr, int target) {int i = 0, j = arr.length;//理解：j指向的不参与比较,因为j目前指向是nullwhile (i < j) { //因为j是不参与比较，如果要是i=j这种情况发生会陷入死循环int mid = (i + j) >>> 1;  // int mid = (i + j) / 2  使用>>>1(无符号右移)是为了防止超出正整数表示范围导致结果为负if(target < arr[mid]) {j = mid;//如果是mid - 1会导致因为右侧开区间计算mid后mid - 1会漏掉mid - 1这个索引元素，因为j指向的索引元素不参与比较}else if(arr[mid] < target) {i = mid + 1;}else{return mid;}}return -1;}//mainpublic static void main(String[] args) {int[] a = {1,2,3,4,5,6,7,8,9,10};System.out.println(binarySearch(a, 10)); //输出：9}
}

总结：

二分查找是一个优秀的查找算法，能够高效的对有序数组进行查找指定元素位置，以至于我们在这种对于有序数组快速定位元素位置可以使用二分查找算法。但是 Java 有自己封装好的二分查找算法：Arrays.binarySearch(arrayList,target)

这个内部封装好的方法除了会找到目标值位置，如果在有序数组内没有找到目标值，那么就会按照下面的公式进行返回值：- (插入点 + 1)，所以我们可以通过这个返回时来反向算出目标值插入位置。

import java.util.Arrays;public class BinarySearchSecond {public static void main(String[] args) {int target = 1;int[] arrayList = {1,2,3,4,5,6,7,8};int i = Arrays.binarySearch(arrayList,target);System.out.println(i);//如果找不到就会按照-(插入点+1)返回,也可以通过这个找到想要插入的不重复数字的位置}
}

http://www.ppmy.cn/server/124720.html

相关文章

成功使用DDNS动态域名访问我的群晖NAS（TP-link路由器）

成功使用DDNS动态域名访问我的群晖NAS（TP-link路由器）

当NAS设备部署在动态IP环境中&#xff08;如家庭或小型办公室宽带&#xff09;&#xff0c;远程访问常常受到IP地址频繁变动的困扰。为了解决这一问题&#xff0c;结合神卓互联NAS公网助手提供的DDNS&#xff08;动态域名服务&#xff09;功能&#xff0c;我们可以轻松实现通过…
阅读更多...
Vscode超好看的渐变主题插件

Vscode超好看的渐变主题插件

样式效果&#xff1a; 插件使用方法&#xff1a; 然后重启&#xff0c;之后会显示vccode损坏&#xff0c;不用理会&#xff0c;因为这个插件是更改了应用内部代码&#xff0c;直接不再显示即可。
阅读更多...
ubuntu命令行设置wifi和宽带连接

ubuntu命令行设置wifi和宽带连接

在Ubuntu中&#xff0c;你可以使用命令行工具来设置Wi-Fi和宽带连接。以下是具体的步骤&#xff1a; 设置Wi-Fi连接 1. 使用 nmcli 工具 nmcli 是一个用于控制NetworkManager并报告其状态的命令行工具。 查看可用的Wi-Fi网络&#xff1a; nmcli dev wifi list连接到Wi-Fi网络…
阅读更多...
轻量级日志管理系统SpringBoot3+Loki+grafana的使用实例

轻量级日志管理系统SpringBoot3+Loki+grafana的使用实例

目录 文章目录 目录1、简介2、SpringBoot3应用发送日志到Loki2.1、基本介绍2.2、添加依赖2.3、配置文件application.yml2.4、创建logback配置2.5、添加日志示例2.6、运行SpringBoot3 3、在grafana中查看日志3.1、登录grafana3.2、查询日志3.3、查询我们的SpringBoot发送过来的日…
阅读更多...
lua基础语法

lua基础语法

Lua 是一种轻量级的脚本语言&#xff0c;它以其简洁和灵活性而闻名。以下是 Lua 基础语法的一些关键点&#xff1a; 1. 变量声明 Lua 中的变量声明需要使用 local 关键字&#xff0c;表示变量的作用域仅限于当前区块。 local x 10 -- 局部变量 x 20 -- 全局变量&a…
阅读更多...
uniapp 动态修改input样式

uniapp 动态修改input样式

最近在用HBuilderx工具开发蓝牙调试工具&#xff0c;项目采用uniapp、vue3.0架构&#xff0c;需求设计为在向蓝牙模块发送数据之前&#xff0c;监测input是否为空&#xff0c;如果为空&#xff0c;则input边框橙红色。界面如下图所示&#xff1a; uniapp架构采用 .vue格式文件&…
阅读更多...
uniapp路由跳转

uniapp路由跳转

一、uni.navigateTo(object) 保留当前页面&#xff0c;跳转到指定非tabBar页面&#xff0c;如&#xff1a; uni.navigateTo({url:/pages/demo1/demo1, }) 二、uni.redirectTo(object) 关闭当前页面&#xff0c;跳转到指定非tabBar页面&#xff0c;如&#xff1a; uni.redi…
阅读更多...
19 基于51单片机的倒计时音乐播放系统设计

19 基于51单片机的倒计时音乐播放系统设计

目录 一、主要功能 二、硬件资源 三、程序编程 四、实现现象 一、主要功能 五个按键&#xff0c;分别为启动按键&#xff0c;则LCD1602显示倒计时&#xff0c;音乐播放 设置按键&#xff0c;可以设置倒计时的分秒&#xff0c;然后加减按键&#xff0c;还有最后一个暂停音乐…
阅读更多...
最新文章

Copyright @ 2022~2023