二分查找

这篇具有很好参考价值的文章主要介绍了二分查找。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

二分查找

简介

二分查找(Binary Search)是一种高效的搜索算法,用于在 有序数组(或有序列表) 中查找特定元素的位置。它将目标值与数组的中间元素进行比较,并根据比较结果缩小搜索范围,直到找到目标值或确定目标值不存在。

二分查找的关键点是每次迭代都能将搜索范围缩小一半,因此其时间复杂度为 O(log n) ,其中 n 是数组的长度。这使得二分查找成为处理大规模有序数据集的有效算法。

代码演示

二分查找的基本思想:

  1. 首先,确定数组的左边界 left 和右边界 right ,通常初始时 left = 0right = 数组长度 - 1
  2. 在每一次迭代中,计算中间元素的索引 mid ,使用 floor 函数将中间值可能的小数部分向下向下取整。
  3. 将目标值与中间元素 nums[mid] 进行比较:
    • 如果 nums[mid] 等于目标值,表示找到了目标值,返回 mid
    • 如果 nums[mid] 大于目标值,表示目标值可能在左侧,更新查询边界 right = mid - 1
    • 如果 nums[mid] 小于目标值,表示目标值可能在右侧,更新查询边界 left = mid + 1
  4. 重复执行步骤 2 和步骤 3,直到找到目标值或搜索范围为空( left > right ),此时目标值不存在,返回 -1。

以下是 JavaScript 代码演示:

function binarySearch(nums, target) {
    let left = 0;
    let right = nums.length - 1;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (nums[mid] === target) {
            return mid;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

进阶练习

LeetCode - 搜索插入位置文章来源地址https://www.toymoban.com/news/detail-540550.html

到了这里,关于二分查找的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 二叉搜索树(Binary Search Tree,BST)

    二叉搜索树(Binary Search Tree),也称二叉查找树或二叉排序树,是一种特殊的二叉树,它满足以下性质 对于二叉搜索树的每个节点 左子树中的所有节点的值都小于该节点的值 右子树中的所有节点的值都大于(或等于)该节点的值 对于二叉搜索树的任意节点,其左子树和右子

    2024年02月09日
    浏览(45)
  • 【C++】二叉搜索树Binary Search Tree

    二叉搜索树又被称为二叉排序树,顾名思义,当我们使用中序遍历时,会得到一个有序的序列。二叉搜索树有如下的性质: 1.若它的左子树不为空,则左子树上每个节点的值都小于根节点的值。 2.若它的右子树不为空,则右子树上每个节点的值都大于根节点的值。 3.左右子树

    2024年02月07日
    浏览(48)
  • 二叉搜索树(Binary_Search_Tree)

    二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树: 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值。 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值。 它的左右子树也分别为二叉搜索树。 如: a、从根开始

    2024年04月28日
    浏览(39)
  • 最优二叉搜索树(Optimal Binary Search Tree)_20230401

    前言 如果有序数组或有序表中的各个元素查找概率相等,那么采用二叉搜索树(BST)进行折半查找,性能最优。如果有序表中各个记录的查找概率不相等,情况又如何呢? 先看一个具体例子。已知有序表keys, 同时给出各个元素的查询频率,注意到各个元素的查询频率不相同。

    2024年02月12日
    浏览(51)
  • 【C++庖丁解牛】二叉搜索树(Binary Search Tree,BST)

    🍁你好,我是 RO-BERRY 📗 致力于C、C++、数据结构、TCP/IP、数据库等等一系列知识 🎄感谢你的陪伴与支持 ,故事既有了开头,就要画上一个完美的句号,让我们一起加油 二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树: 若它的左子树不为空,

    2024年03月28日
    浏览(64)
  • 浙大数据结构第四周之04-树6 Complete Binary Search Tree

    A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties: The left subtree of a node contains only nodes with keys less than the node\\\'s key. The right subtree of a node contains only nodes with keys greater than or equal to the node\\\'s key. Both the left and right subtrees must also be binary search trees. A Comple

    2024年02月16日
    浏览(49)
  • 数据结构英文习题解析-第五章 二叉搜索树Binary Search Tree

    前言:最近快到FDS考试了,po重刷了一下学校的题目,自己整理了一些解析orz 因为po在自己找解析和学习的过程中非常痛苦,所以在此共享一下我的题目和自己写的解题思路,欢迎各位指出错误~全章节预计会陆续更新,可在专栏查看~ HW5 1.In a binary search tree, the keys on the same

    2024年04月09日
    浏览(48)
  • 数据结构第四天: Complete Binary Search Tree 【搜索二叉树,完全二叉树】

     这道题需要的操作时排序并且需要遍历,最重要的一点它是个完全二叉树,所以数组是最适合的 这道题我的思路来自于浙江大学课件7.0.2完全二叉树 这道题说白就是将输入的样例构造成一个完全搜索二叉树。因为完全线索二叉树的 根节点一定是是一个处于左右子树中间的那

    2024年02月06日
    浏览(54)
  • Leetcode 1011. Capacity To Ship Packages Within D Days (Binary Search经典)

    Capacity To Ship Packages Within D Days Medium 8.6K 179 Companies A conveyor belt has packages that must be shipped from one port to another within days days. The ith package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maxi

    2024年02月09日
    浏览(33)
  • 问题 C: 二分查找右侧边界(C++)(二分查找)

    1.题目描述 2.AC 问题 C: 二分查找右侧边界 时间限制: 1.000 Sec  内存限制: 128 MB 提交 状态 题目描述 请在一个有序不递减的数组中(数组中的值有相等的值),采用二分查找,找到最后1次出现值x的位置,如果不存在x请输出-1。 请注意:本题要求出q个x,每个x在数组中第一

    2024年02月03日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包