算法通关村——透彻理解二分查找

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

1. 循环法

    public static int binarySearch(int[] arr, int low, int high, int target) {
        while (low <= high) {
            // 这样写主要是避免溢出的情况,以及>>优先级小于+,避免出现死循环
            int mid = low + ((high - low) >> 1);
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }

2. 递归

    public static int binarySearch1(int[] array, int low, int high, int target) {
        if (low < high) {
            int mid = low + ((high - low) >> 1);
            if (array[mid] == target) {
                return mid;
            } else if (array[mid] > target) {
                return binarySearch(array, low, mid - 1, target);
            } else {
                return binarySearch(array, mid + 1, high, target);
            }
        }
        return -1;
    }

3. 元素中有重复的二分查找

假设现在有个数组里面有重复元素,并且按照增序排列,如果有相同元素,返回最左侧的第一个重复元素的位置。

核心思路也是比较简单了,当找到第一个重复的元素时候,记录位置,然后向左移动,左边的不是目标元素,就意味着左边没有重复的目标元素,然后+1就是目标元素的位置文章来源地址https://www.toymoban.com/news/detail-643569.html

 public static int search(int[] nums, int target) {
        if (nums == null || nums.length == 0)
            return -1;
        int low = 0;
        int high = nums.length - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (nums[mid] < target) {
                low = mid + 1;
            } else if (nums[mid] > target) {
                high = mid - 1;
            } else {
                // 找到了符合目标元素的数据位置,然后一直往左遍历,知道不是目标元素或者索引为0的时候停止
                while (mid != 0 && nums[mid] == target) {
                    mid--;
                }
                if (mid == 0 && nums[mid] == target) {
                    return mid;
                }
                return mid + 1;
            }
        }
        return -1;
    }

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

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

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

相关文章

  • 数据结构,查找算法(二分,分块,哈希)

    一、查找算法         1、二分查找:(前提条件: 必须有序的序列) 2、分块查找:(块间有序,块内无序)     索引表  +  源数据表     思路:     (1)先在索引表中确定在哪一块中     (2)再遍历这一块进行查找 //索引表 typedef  struct  {     int max; //块中最大值

    2024年02月11日
    浏览(59)
  • Python数据结构与算法篇(五)-- 二分查找与二分答案

    1.1 定义         二分查找又称折半查找、二分搜索、折半搜索等,是一种在静态查找表中查找特定元素的算法。         所谓静态查找表,即只能对表内的元素做查找和读取操作,不允许插入或删除元素。         使用二分查找算法,必须保证查找表中存放的是有

    2023年04月20日
    浏览(47)
  • 【数据结构与算法】python实现二分查找

    二分查找 又称折半查找,它是一种效率较高的查找方法 原理:首先,假设表中元素是按升序排列,将表中间位置记录的与查找比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的大于查找,则

    2024年02月05日
    浏览(40)
  • 数据结构和算法之二分法查找

    二分法查找,也称作 二分查找 或 折半查找 ,是一种在有序数组中快速查找特定元素的算法。它采用分治法思想,通过将问题划分为规模更小的子问题,并且通过对子问题的查找来解决原问题。 二分法查找的思路是不断地将数组一分为二,然后判断目标值在哪一部分,进而

    2024年02月09日
    浏览(48)
  • Java【数据结构】二分查找

    🌏在 有序 数组A中,查找目标值target 🌏如果找到返回索引 🌏如果找不到返回-1 算法描述 解释 前提 给定一个内含n个元素的有序数组A,满足A0=A1=A2=·······=An-1,一个待查值target 1 设置left=0;right = n - 1 2 如果left right ,结束查找,没找到 3 设置mid = (left + right )/2,mid为中间

    2024年02月12日
    浏览(49)
  • 数据结构-查找(顺序查找与二分查找的讲解与代码实现)

    顺序查找概念:从表的另一端开始,一次将记录的和给定值进行比较,若某个记录的和给定的值相等,则查找成功,反之则查找失败。 ASL:平均查找长度 pi查找概率,ci查找次数 eg:序列1,2,3 查找1的次数为1概率为1/3,2为两次概率1/3,3的次数为3概率1/3  将12

    2024年02月06日
    浏览(69)
  • 【手撕数据结构】二分查找(好多细节)

    🌈键盘敲烂,年薪30万🌈 目录 普通版本的二分查找: right只负责控制边界(少了两次比较): 时间复杂度更稳定的版本: BSLeftmost: BSRightmost:   🏸细节1:循环判定条件是left = right ⭐细节2:mid = (left + right ) 1 原因见代码注释 改动1:while条件是left right 改动2:right = nums.len

    2024年02月05日
    浏览(47)
  • 浙大数据结构第一周01-复杂度3 二分查找

    本题要求实现二分查找算法。 函数接口定义: 其中 List 结构定义如下: L 是用户传入的一个线性表,其中 ElementType 元素可以通过、==、进行比较,并且题目保证传入的数据是递增有序的。函数 BinarySearch 要查找 X 在 Data 中的位置,即数组下标(注意:元素从下标1开始存储)

    2024年02月12日
    浏览(47)
  • 说说你对二分查找的理解?如何实现?应用场景?

      在计算机科学中,二分查找算法,也称折半搜索算法,是一种在有序数组中查找某一特定元素的搜索算法 想要应用二分查找法,则这一堆数应有如下特性: 存储在数组中 有序排序 搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束 如果

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

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

    2024年02月11日
    浏览(52)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包