逢试必考的二分查找(算法村第九关青铜挑战)

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

位运算

除法在计算机中效率很低,一般改用 >> x ,意思是二进制数的每个位右移 x 位。从十进制的角度看, x 是以 2 为底的指数,这个指数就是除数。

//等价式
mid = (low + high) / 2;
mid = low + high >> 2;	//效率提高
mid = low + (high - low >> 2);	//防止(low + high)溢出

在 Java 中,位运算符 >> 的优先级低于加法运算符 +,所以需要使用括号来保证正确的优先级文章来源地址https://www.toymoban.com/news/detail-813971.html

用递归实现二分查找

/**
 * @param arr 升序数组
 */
public static int binarySearch(int[] arr, int low, int high, int target)
{
    if(low > high)
        return -1;  //没有找到返回-1

    int mid = low + (high - low >> 1);

    if(arr[mid] == target)
        return mid; //返回目标值的位置

    else if(arr[mid] < target)
        return binarySearch(arr,mid + 1, high, target); //向右寻找

    else
        return binarySearch(arr, low, mid - 1, target); //向左寻找
}

有重复元素的二分查找

迭代实现

public static int binarySearch(int[] arr, int target)
{
    int low = 0;
    int high = arr.length - 1;

    // 使用二分查找法查找target
    while (low <= high)
    {
        int mid = low + (high - low >> 1);

        // 如果中间元素等于target,则返回中间元素索引
        if (arr[mid] == target)
        {
            // 如果中间元素不是第一个元素,则继续向前查找
            while (mid != 0 && arr[mid] == target)
                mid--;

            // 如果中间元素是第一个元素,则返回0
            if (mid == 0)
                return 0;
            else
                return mid + 1;
        }
        // 如果中间元素小于target,则将low移动到mid+1
        else if (arr[mid] < target)
            low = mid + 1;
        // 如果中间元素大于target,则将high移动到mid-1
        else
            high = mid - 1;
    }

    // 如果查找结束没有找到target,则返回-1
    return -1;
}

到了这里,关于逢试必考的二分查找(算法村第九关青铜挑战)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 算法通关村第九关——中序遍历与搜索树

    二叉搜索树按照中序遍历正好是一个递增序列。其比较规范的定义是: 若它的左子树不为空,则左子树上所有节点的值均小于它的根节点的值; 若它的右子树不为空,则右子树所有节点的值均大于它的根节点的值; 它的左、右子树也分别为二叉搜索树,比如下面的例子:

    2024年02月11日
    浏览(36)
  • 【算法系列篇】二分查找——这还是你所知道的二分查找算法吗?

    在生活中,我们往往会遇到在数组中查找某个确定的元素的时候,通常我们会选择使用暴力解法,这样虽然简单,但是时间复杂度是O(N),时间效率比较低。那么是否有方法可以使得在具有二段性的数组中找某一特定的元素的时间复杂度低于0(N)呢?答案是肯定的,当我们可以

    2024年02月11日
    浏览(52)
  • 【算法系列 | 8】深入解析查找算法之—二分查找

    心若有阳光,你便会看见这个世界有那么多美好值得期待和向往。 决定开一个算法专栏,希望能帮助大家很好的了解算法。主要深入解析每个算法,从概念到示例。 我们一起努力,成为更好的自己! 今天第8讲,讲一下查找算法的二分查找 查找算法是很常见的一类问题,主

    2024年02月07日
    浏览(55)
  • C++二分算法(二分查找&二分答案)细节详解

     二分算法可以分为 二分查找 和 二分答案 。 以在一个 升序数组 中查找一个数为例。它每次考察数组当前部分的 中间元素 ,如果中间元素刚好是要找的,就结束搜索过程;如果中间元素小于所查找的值,那么左侧的只会更小,不会有所查找的元素,只需到右侧查找;如果

    2024年02月08日
    浏览(53)
  • 【算法】二分查找(整数二分和浮点数二分)

    大家好!今天我们来学习二分查找算法,这是一种效率很高的算法哦! 目录 1. 整数二分 2. 整数二分模板 3. 整数二分模板题 3.1 洛谷 P2249 【深基13.例1】查找 3.2 Acwing789. 数的范围 4. 浮点数二分 5. 浮点数二分模板 6. 浮点数二分模板题 6.1 Acwing 790.数的三次方根 6.2 洛谷 P1024 [

    2024年02月10日
    浏览(52)
  • 【Python查找算法】二分查找、线性查找、哈希查找

    目录 1 二分查找算法  2 线性查找算法 3 哈希查找算法         二分查找(Binary Search)是一种用于在有序数据集合中查找特定元素的高效算法。它的工作原理基于将数据集合分成两半,然后逐步缩小搜索范围,直到找到目标元素或确定目标元素不存在。 以下是二分查找的

    2024年02月08日
    浏览(52)
  • 【算法】简单的二分查找算法

    一个简单的二分查找算法:         简单描述:算法由静态方法rank()实现,它接受一个整数键和一个有序的int数组作为参数,如果整数存在于数组,返回它的索引,否则返回-1,算法使用两个变量lo和hi,并保证整数如果存在于数组中则它一定存在于a[lo...hi]中,然后通过循

    2024年01月21日
    浏览(57)
  • 【算法小课堂】二分查找算法

    当我们要从一个序列中查找一个元素的时候,最快想到的方法就是顺序查找法(即:从前到后依次查找)。但这种方法过于无脑,就是暴力的把每个元素都排查一遍。元素个数少的时候还行,一旦元素个数多起来,效率是非常低下,所以在实际中这种查找的方法是被摒弃的。

    2024年02月08日
    浏览(39)
  • Java数据结构与算法:查找算法之二分查找

    大家好,我是免费搭建查券返利机器人赚佣金就用微赚淘客系统3.0的小编,欢迎回到本专栏。在这个冰冷的季节里,我们将一同探讨Java中一种高效的查找算法——二分查找。让我们点燃知识的火花,一同解锁这个查找奇迹的秘密! 二分查找简介 二分查找,也称为折半查找,

    2024年01月21日
    浏览(47)
  • 数据结构算法--1 顺序查找二分查找

    顺序查找时间复杂度为O(n) 我们可以借助Python中的函数enumerate,通过enumerate遍历列表返回其索引和值 也可以通过列表长度依次遍历: 但是二分查找时间复杂度为O(logn):

    2024年02月12日
    浏览(54)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包