【算法优选】 二分查找专题——壹

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

😎前言

二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列

查找过程

首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。

算法要求

1.必须采用顺序存储结构。
2.必须按关键字大小有序排列。

比较次数

计算公式:
当顺序表有n个关键字时:
查找失败时,至少比较a次关键字;
查找成功时,最多比较关键字次数是b。
注意:a,b,n均为正整数。

算法复杂度

二分查找的基本思想是将n个元素分成大致相等的两部分,取a[n/2]与x做比较,如果x=a[n/2],则找到x,算法中止;如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x.
时间复杂度即是while循环的次数。
总共有n个元素,
渐渐跟下去就是n,n/2,n/4,…n/2^k(接下来操作元素的剩余个数),其中k就是循环的次数
由于你n/2^k取整后>=1
即令n/2^k=1
可得k=log2n,(是以2为底,n的对数)
所以时间复杂度可以表示O(h)=O(log2n)

🎋二分查找

🚩题目描述:

给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。

  • 示例 1:
    输入: nums = [-1,0,3,5,9,12], target = 9
    输出: 4
    解释: 9 出现在 nums 中并且下标为 4

  • 示例 2:
    输入: nums = [-1,0,3,5,9,12], target = 2
    输出: -1
    解释: 2 不存在 nums 中因此返回 -1

class Solution {
    public int search(int[] nums, int target) {

    }
}

🚩算法流程:

  1. 定义 left , right 指针,分别指向数组的左右区间。
  2. 找到待查找区间的中间点 mid ,找到之后分三种情况讨论:
  • arr[mid] == target 说明正好找到,返回 mid 的值;
  • arr[mid] > target 说明 [mid, right] 这段区间都是⼤于 target 的,因此舍去右边区间,在左边 [left, mid -1] 的区间继续查找,即让 right = mid -1 ,然后重复 2 过程;
  • arr[mid] < target 说明 [left, mid] 这段区间的值都是⼩于 target 的,因此舍去左边区间,在右边 [mid + 1, right] 区间继续查找,即让 left = mid +1 ,然后重复 2 过程;
  1. 当 left 与 right 错开时,说明整个区间都没有这个数,返回 -1 。

🚩代码实现:

class Solution {
    public int search(int[] nums, int target) {
        // 初始化 left 与 right 指针
        int left = 0;
        int right = nums.length - 1;
        // 由于两个指针相交时,当前元素还未判断,因此需要取等号
        while (left <= right) {
            // 先找到区间的中间元素
            int mid = left + (right - left) / 2;
            // 分三种情况讨论
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        // 如果程序⾛到这⾥,说明没有找到⽬标值,返回 -1
        return -1;
    }
}

🌴在排序数组中查找元素的第一个和最后一个位置

🚩题目描述

给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target,返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

  • 示例 1:
    输入:nums = [5,7,7,8,8,10], target = 8
    输出:[3,4]

  • 示例 2:
    输入:nums = [5,7,7,8,8,10], target = 6
    输出:[-1,-1]

  • 示例 3:
    输入:nums = [], target = 0
    输出:[-1,-1]

class Solution {
    public int[] searchRange(int[] nums, int target) {

    }
}

🚩算法思路:

⽤的还是⼆分思想,就是根据数据的性质,在某种判断条件下将区间⼀分为⼆,然后舍去其中⼀个区间,然后再另⼀个区间内查找;

⽅便叙述,⽤ x 表⽰该元素, resLeft 表⽰左边界, resRight 表⽰右边界。

📌寻找左边界思路:

寻找左边界:

  • 我们注意到以左边界划分的两个区间的特点:

左边区间 [left, resLeft - 1] 都是⼩于 x 的;

右边区间(包括左边界) [resLeft, right] 都是⼤于等于 x 的;

因此,关于 mid 的落点,我们可以分为下⾯两种情况:

  • 当我们的 mid 落在 [left, resLeft - 1] 区间的时候,也就是 arr[mid] <target 。说明 [left, mid] 都是可以舍去的,此时更新 left 到 mid + 1 的位置,继续在 [mid + 1, right] 上寻找左边界;

  • 当 mid 落在 [resLeft, right] 的区间的时候,也就是 arr[mid] >= target 。说明 [mid + 1, right] (因为 mid 可能是最终结果,不能舍去)是可以舍去的,此时更新 right 到 mid 的位置,继续在 [left, mid] 上寻找左边界

由此,就可以通过⼆分,来快速寻找左边界;

注意:这⾥找中间元素需要向下取整

因为后续移动左右指针的时候:

  • 左指针: left = mid + 1 ,是会向后移动的,因此区间是会缩⼩的;

  • 右指针: right = mid ,可能会原地踏步(⽐如:如果向上取整的话,如果剩下 1,2 两个元素, left == 1 ,right == 2 , mid == 2 。更新区间之后, left,right,mid 的值没有改变,就会陷⼊死循环)。因此⼀定要注意,当 right = mid 的时候,要向下取整

📌寻找右边界思路:

寻右左边界:

  • ⽤ resRight 表⽰右边界;
  • 我们注意到右边界的特点:
    ▪ 左边区间(包括右边界) [left, resRight] 都是⼩于等于 x 的;
    ▪ 右边区间 [resRight+ 1, right] 都是⼤于 x 的;

因此,关于 mid 的落点,我们可以分为下⾯两种情况:

  • 当我们的 mid 落在 [left, resRight] 区间的时候,说明 [left, mid - 1]( mid 不可以舍去,因为有可能是最终结果)都是可以舍去的,此时更新left 到 mid 的位置;
  • 当 mid 落在 [resRight+ 1, right] 的区间的时候,说明 [mid, right] 内的元素
    是可以舍去的,此时更新 right 到 mid - 1 的位置;

由此,就可以通过⼆分,来快速寻找右边界;

注意:这⾥找中间元素需要向上取整。

因为后续移动左右指针的时候:

  • 左指针: left = mid ,可能会原地踏步(⽐如:如果向下取整的话,如果剩下 1,2 两个元素, left == 1, right == 2,mid == 1 。更新区间之后, left,right,mid 的值没有改变,就会陷⼊死循环)。

  • 右指针: right = mid - 1 ,是会向前移动的,因此区间是会缩⼩的;

因此⼀定要注意,当 right = mid 的时候,要向下取整

🚩代码实现

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] ret = new int[2];
        ret[0] = ret[1] = -1;
        // 处理边界情况
        if(nums.length == 0) {
            return ret;
        }
        // 1. ⼆分左端点
        int left = 0;
        int right = nums.length - 1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        // 判断是否有结果
        if(nums[left] != target) {
            return ret;
        } else {
            ret[0] = right;
        }
        // 2. ⼆分右端点
        left = 0; 
        right = nums.length - 1;
        while(left < right) {
            int mid = left + (right - left + 1) / 2;
            if(nums[mid] <= target) {
                left = mid;
            }else {
                right = mid - 1;
            }
        }
        ret[1] = left;
        return ret;
    }
}

🌳搜索插入位置

🚩题目描述

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

  • 示例 1:
    输入: nums = [1,3,5,6], target = 5
    输出: 2

  • 示例 2:
    输入: nums = [1,3,5,6], target = 2
    输出: 1

  • 示例 3:
    输入: nums = [1,3,5,6], target = 7
    输出: 4

class Solution {
    public int searchInsert(int[] nums, int target) {

    }
}

🚩算法思路:

1、分析插⼊位置左右两侧区间上元素的特点:

设插⼊位置的坐标为 index ,根据插⼊位置的特点可以知道:

  • [left, index - 1] 内的所有元素均是⼩于 target 的;

  • [index, right] 内的所有元素均是⼤于等于 target 的。

2、设 left 为本轮查询的左边界, right 为本轮查询的右边界。根据 mid 位置元素的信
息,分析下⼀轮查询的区间:

  • 当 nums[mid] >= target 时,说明 mid 落在了 [index, right] 区间上,mid 左边包括 mid 本⾝,可能是最终结果,所以我们接下来查找的区间在 [left,mid] 上。因此,更新 right 到 mid 位置,继续查找。
  • 当 nums[mid] < target 时,说明 mid 落在了 [left, index - 1] 区间上,mid 右边但不包括 mid 本⾝,可能是最终结果,所以我们接下来查找的区间在 [mid + 1, right] 上。因此,更新 left 到 mid + 1 的位置,继续查找。

3、 直到我们的查找区间的⻓度变为 1 ,也就是left == right 的时候, left 或者
right 所在的位置就是我们要找的结果

🚩代码实现:

    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } 
            else {
                right = mid;
            }
        }
        // 特判⼀下第三种情况
        if (nums[right] < target) {
            return right + 1;
        }
        return right;
    }

🎄x的平方根

🚩题目描述

给你一个非负整数 x ,计算并返回 x 的 算术平方根 。

由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。

注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。

  • 示例 1:
    输入:x = 4
    输出:2
  • 示例 2:
    输入:x = 8
    输出:2
    解释:8 的算术平方根是 2.82842…, 由于返回类型是整数,小数部分将被舍去。
class Solution {
    public int mySqrt(int x) {
        
    }
}

🚩算法思路:

设 x 的平⽅根的最终结果为 index :

分析 index 左右两次数据的特点:

  • [0, index] 之间的元素,平⽅之后都是⼩于等于 x 的;

  • [index + 1, x] 之间的元素,平⽅之后都是⼤于 x 的。

因此可以使⽤⼆分查找算法。

🚩代码实现:

class Solution {
    public int mySqrt(int x) {
        long left = 1;
        long right = x;
        if(x < 1) {
            return 0;
        }
        while(left < right) {
            long mid = left + (right - left + 1)/2;
            if(mid*mid <= x) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return (int)left;
    }
}

⭕总结

关于《【算法优选】 二分查找专题——壹》就讲解到这儿,感谢大家的支持,欢迎各位留言交流以及批评指正,如果文章对您有帮助或者觉得作者写的还不错可以点一下关注,点赞,收藏支持一下!文章来源地址https://www.toymoban.com/news/detail-716242.html

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

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

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

相关文章

  • Java数据结构与算法:查找算法之二分查找

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

    2024年01月21日
    浏览(46)
  • java实现二分查找算法

    递归实现: public static int binarySearchRecursive(int[] arr, int target) {     return binarySearchRecursive(arr, target, 0, arr.length - 1); }   private static int binarySearchRecursive(int[] arr, int target, int low, int high) {     if (low high) {         return -1; // 没有找到目标元素     }          int mid = (low + high) / 2

    2024年04月09日
    浏览(44)
  • c语言经典算法—二分查找,冒泡,选择,插入,归并,快排,堆排

             1、前提条件:数据有序,随机访问;          2、实现:递归实现,非递归实现          3、注意事项:                 循环退出条件:low =high,low = high.说明还有一个元素,该元素还要与key进行比较                 mid的取值:mid=(low + high)/2;mid = l

    2024年02月05日
    浏览(45)
  • 算法与人生 揭秘C语言中高效搜索的秘诀——二分查找算法详解

    引言,少年们,大家好。在这里祝大家元旦快乐,我是博主 那一脸阳光 ,今天来介绍二分查找 在计算机科学领域,搜索算法是数据处理和问题解决的重要工具之一。其中,**二分查找算法(Binary Search)**以其卓越的时间复杂度和简洁高效的实现,在众多搜索算法中脱颖而出

    2024年01月17日
    浏览(59)
  • Java-三个算法冒泡-选择排序,二分查找

    Java算法: 冒泡排序; 解析:将前后两个数对比,将大的数(或小的)调换至后面,每轮将对比过程中的最大(或最小)数,调到最后面。每轮对比数减一;初始对比数为数组长度-1. 选择排序: 解析:选择第一个数依次与其他元素对比,数值小的或(大的)交换位置至前方(

    2024年02月11日
    浏览(40)
  • 【算法优选】双指针专题——贰

    常⻅的双指针有两种形式,⼀种是 对撞指针 ,⼀种是 左右指针 对撞指针 :⼀般⽤于顺序结构中,也称左右指针。 对撞指针从两端向中间移动。⼀个指针从最左端开始,另⼀个从最右端开始,然后逐渐往中间逼近。 对撞指针的终⽌条件⼀般是两个指针相遇或者错开(也可能

    2024年02月08日
    浏览(52)
  • 【算法优选】 滑动窗口专题——壹

    基本概念 滑动窗口是一种 基于双指针 的一种思想,两个指针指向的元素之间形成一个窗口。 分类:窗口有两类,一种是 固定大小类 的窗口,一类是 大小动态变化 的窗口。 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其总和大于等于 target 的长

    2024年02月08日
    浏览(40)
  • 【算法优选】前缀和专题——叁

    含义 : 前缀和实际上就是对于长度为n的数组, 我们新建立一个数组长度为n+1,第i个元素的值为前i个元素的和(包括第i个元素) 。 特点 : 前缀和数组比原数组多一个长度。 前缀和的第0个元素的值为0。 根据前缀和数组的特点,求前缀和时。我们只需要用第i个元素的值

    2024年02月06日
    浏览(44)
  • 【算法优选】 前缀和专题——壹

    含义 : 前缀和实际上就是对于长度为n的数组, 我们新建立一个数组长度为n+1,第i个元素的值为前i个元素的和(包括第i个元素) 。 特点 : 前缀和数组比原数组多一个长度。 前缀和的第0个元素的值为0。 根据前缀和数组的特点,求前缀和时。我们只需要用第i个元素的值

    2024年02月08日
    浏览(39)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包