首页 星云 工具 资源 星选 资讯 热门工具
:

PDF转图片 完全免费 小红书视频下载 无水印 抖音视频下载 无水印 数字星空

清晰易懂二分查找算法 你确定不看吗?

编程知识
2024年08月08日 14:56

@

目录


前言

请各大网友尊重本人原创知识分享,谨记本人博客:南国以南i


提示:以下是本篇文章正文内容,下面案例可供参考

简介

二分查找 (Binary Search) 是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到元素。

二分查找算法的效率很高,时间复杂度为O(log n),其中n是数组中的元素数量。这是因为每次比较后,搜索范围都会减半。

一、二分查找算法的原理是什么?

二分查找算法(Binary Search Algorithm)的原理基于分治法的思想,用于在有序数组中快速查找某一特定元素的位置。其核心原理可以概括为以下几个步骤:

1. 确定搜索范围:

首先,确定搜索的起始位置 low 和结束位置 high,这两个位置分别指向数组的第一个元素和最后一个元素。这样,就确定了整个搜索范围。

2. 计算中间位置:

在每次迭代中,计算搜索范围的中间位置 mid ,这通常是通过将 lowhigh 相加后除以2来实现的(注意防止整数溢出,更安全的写法是 mid = low+ ( high - low ) / 2 )。

3. 比较中间元素:

将中间位置上的元素与要查找的目标值 target 进行比较。

4. 调整搜索范围:

  • 如果中间元素正好是要查找的目标值,则查找成功,返回中间位置的索引。
  • 如果中间元素大于目标值,则说明目标值位于当前搜索范围的左半部分,因此将high更新为 mid - 1,以缩小搜索范围到左半部分。
  • 如果中间元素小于目标值,则说明目标值位于当前搜索范围的右半部分,因此将low更新为 mid + 1,以缩小搜索范围到右半部分。

5. 重复迭代:

重复步骤2至步骤4,直到找到目标值或搜索范围为空(即 low> high )。如果搜索范围为空,则说明数组中不存在目标值,此时可以返回-1或其他表示未找到的值。

二分查找算法之所以高效,是因为它每次迭代都将搜索范围减半,从而显著减少了需要比较的元素数量。在最坏的情况下(即目标值不存在于数组中),二分查找算法的时间复杂度为O(log n),其中n是数组中的元素数量。这使得二分查找成为处理大数据集时非常有用的工具。

需要注意的是,二分查找算法要求数组必须是有序的。如果数组无序,则需要先对其进行排序,但这可能会增加总体的时间复杂度。因此,二分查找通常用于已经排序的数组或可以在查找之前进行排序的场景中。

二、二分查找算法的优缺点是什么?

二分查找算法(Binary Search Algorithm)作为一种在有序数组中查找特定元素的算法,具有其独特的优缺点。以下是二分查找算法的主要优缺点:

优点:

  1. 效率高:
    二分查找算法的时间复杂度为O(logn),其中n是数组中的元素数量。这意味着,随着数组大小的增加,查找所需的时间增长非常缓慢,相对于线性查找(时间复杂度为O(n))来说,效率显著提高
  2. 适用范围广:
    只要数据已经排序,就可以使用二分查找算法。这在处理大量数据且需要频繁查找的场景中特别有用,如数据库索引、文件系统中的查找等。
  3. 稳定性好:
    二分查找算法的性能不会受到数组初始排列顺序(只要是有序的)的影响,每次查找的时间复杂度都是O(log n)。

缺点:

  1. 要求数据有序:
    二分查找算法要求数据必须是有序的。如果数据未排序,则需要先进行排序操作,这可能会增加额外的计算开销。在某些情况下,如果排序成本很高,使用二分查找可能并不划算。

  2. 只适用于静态数据集或可快速更新的数据集:
    二分查找算法在查找过程中不修改原数组,因此它特别适用于静态数据集或可以快速更新的数据集。如果数据集频繁变化(如频繁插入或删除元素),则每次变化后都可能需要重新排序或调整索引,这可能会降低二分查找的效率。

  3. 需要额外空间(在某些情况下):
    虽然二分查找算法本身不需要额外的存储空间来保存中间结果(因为它直接在原数组上进行查找),但在某些应用场景下(如需要记录查找路径或进行多次查找时),可能需要额外的数据结构来辅助查找过程。

  4. 对内存敏感:
    由于二分查找依赖于数组的随机访问特性,因此在内存访问速度较慢的环境中(如使用磁盘作为存储介质时),二分查找的效率可能会受到影响。

综上所述,二分查找算法是一种非常高效的查找算法,但它要求数据必须是有序的,并且可能不适用于频繁变化的数据集。在实际应用中,需要根据具体场景和需求来选择是否使用二分查找算法。

三、java 实现二分查找案例

在Java中实现二分查找算法是一个常见的编程任务。以下是一个简单的二分查找算法实现案例,该算法用于在一个有序数组中查找一个特定的元素,并返回其索引。如果未找到该元素,则返回-1。

二叉树

public class BinarySearch {  
  
    /**  
     * 二分查找算法  
     *  
     * @param arr    有序数组  
     * @param target 要查找的目标值  
     * @return 目标值在数组中的索引,如果未找到则返回-1  
     */  
    public static int binarySearch(int[] arr, int target) {  
        int low = 0; // 定义最低点  
        int high = arr.length - 1; // 定义最高点  
  
        while (low <= high) {  
            int mid = low + (high - low) / 2; // 防止溢出,计算中间位置  
            if (arr[mid] == target) {  
                // 找到目标值,返回索引  
                return mid;  
            } else if (arr[mid] < target) {  
                // 目标值在中间位置的右侧,调整最低点  
                low = mid + 1;  
            } else {  
                // 目标值在中间位置的左侧,调整最高点  
                high = mid - 1;  
            }  
        }  
  
        // 未找到目标值,返回-1  
        return -1;  
    }  
  
    public static void main(String[] args) {  
        int[] arr = {-1, 0, 3, 5, 9, 12}; // 示例数组  
        int target = 9; // 要查找的目标值  
  
        int result = binarySearch(arr, target);  
  
        if (result != -1) {  
            System.out.println("元素 " + target + " 在数组中的索引为: " + result);  
        } else {  
            System.out.println("数组中未找到元素 " + target);  
        }  
    }  
}

在这个例子中,binarySearch 方法实现了二分查找算法。它接受一个有序数组 arr 和一个目标值 target 作为参数,并返回目标值在数组中的索引。如果未找到目标值,则返回-1。

在 main 方法中,我们创建了一个示例数组 arr 和一个要查找的目标值 target,然后调用 binarySearch 方法并打印结果。

总结

二分查找算法要求数组是有序的。如果数组未排序,则需要先对其进行排序,然后再使用二分查找算法。此外,二分查找算法的时间复杂度为O(log n),其中n是数组中的元素数量,这使得它在处理大数据集时非常高效。**


我是南国以南i记录点滴每天成长一点点,学习是永无止境的!转载请附原文链接!!!

From:https://www.cnblogs.com/bgyb/p/18349086
本文地址: http://www.shuzixingkong.net/article/913
0评论
提交 加载更多评论
其他文章 Codeforces Round 964 (Div. 4)
Codeforces Round 964 (Div. 4) A送分 B 大意:两个人两张牌 随机翻 求a翻出来的牌比b大的可能 #include &lt;cstdio&gt; #include &lt;cmath&gt; #include &lt;algorithm&gt; #include &lt
vue前端自适应布局,一步到位所有自适应
1,左右布局 - 左侧固定宽带,右侧自适应剩余的宽度。 - 中间一条分割线,可以拖拉,自适应调整左右侧的宽度。 - 左侧的高度超长自动出现横向滚动条,左侧宽度超长,自动出现竖向滚动条。 2,上中下布局 - 最上面的 搜索条件 div 固定占用 100 px 高度,下面的 查询条件 div 固定
vue前端自适应布局,一步到位所有自适应 vue前端自适应布局,一步到位所有自适应
前后端分离项目,后期前端身份验证的麻烦
软件构成 后端 后端是一个asp.netcore webapi项目,使用jwt进行身份验证和鉴权。 前端 前端是一个基于http协议的asp.netcore RezorPage项目,但实际上完全使用的wwwwroot目录下的静态文件。没有使用RazorPage。 目前只有后端接口鉴权,前端页面任意访
前后端分离项目,后期前端身份验证的麻烦 前后端分离项目,后期前端身份验证的麻烦
前端使用 Konva 实现可视化设计器(20)- 性能优化、UI 美化
这一章主要分享一下使用 Konva 遇到的性能优化问题,并且介绍一下 UI 美化的思路,主要使用 Naive UI。
前端使用 Konva 实现可视化设计器(20)- 性能优化、UI 美化 前端使用 Konva 实现可视化设计器(20)- 性能优化、UI 美化
keycloak~关于社区登录的过程说明
keycloak将第三方登录(社区登录)进行了封装,大体主要会经历以下三个过程: 打开社区认证页面,输入账号密码或者扫码,完成社区上的认证 由社区进行302重定向,回到keycloak页面 keycloak与社区完成一次oauth2授权码认证,通过社区返回的code来获取token,再通过token
在 React 项目中 Editable Table 的实现
我们是袋鼠云数栈 UED 团队,致力于打造优秀的一站式数据中台产品。我们始终保持工匠精神,探索前端道路,为社区积累并传播经验价值。 本文作者:佳岚 可编辑表格在数栈产品中是一种比较常见的表单数据交互方式,一般都支持动态的新增、删除、排序等基础功能。 交互分类 可编辑表格一般为两种交互形式: 实时保存
在 React 项目中 Editable Table 的实现 在 React 项目中 Editable Table 的实现 在 React 项目中 Editable Table 的实现
Kotlin 循环与函数详解:高效编程指南
Kotlin中的循环结构让你能轻松遍历数组或范围内的元素。使用`for`循环结合`in`操作符,可以简洁地访问数组中的每个项,如字符串数组或整数数组。对于范围,可以用`..`来定义一系列连续的值并进行迭代。此外,Kotlin支持通过`break`和`continue`控制循环流程。函数则允许封装可复
数据结构 分块 & 莫队
分块 一种优化暴力的思想。 通常是将原数据划分成适当块(一般为 \(\sqrt{n}\)),对每块数据进行预处理,进而达到比暴力更优的时间复杂度。 划分 确定块长后,一般需要开两个数组存储每一块的右边界与原数据所属块序号,更加方便后续操作。 int sq=sqrt(n); for(int i=1;i
数据结构 分块 & 莫队