【趣学算法】Day4 分治算法——二分搜索

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

14天阅读挑战赛
努力是为了不平庸~
算法学习有些时候是枯燥的,这一次,让我们先人一步,趣学算法!

【趣学算法】Day4 分治算法——二分搜索

❤️一名热爱Java的大一学生,希望与各位大佬共同学习进步❤️

🧑个人主页:@周小末天天开心

各位大佬的点赞👍 收藏⭐ 关注✅,是本人学习的最大动力

感谢!

📕该篇文章收录专栏—趣学算法

目录

引入

分治算法要素

分治算法秘籍

二分搜索

算法题目

问题分析

算法步骤

完美图解

算法详解

 算法分析

 (1)时间复杂度:

(2)空间复杂度:


引入

        现实生活中也有很多这样的例子,例如唱歌比赛,如果全国各地的歌手都来报名参赛,那么比赛就需要很长的时间,那怎么办呢?首先全国分赛区海选,然后每个赛区的前几名参加二分“海选”,最后选出比较优秀的选手参加电视节目比赛。这样既能把优秀的歌手呈现给观众,又能节省很多时间,因为全国各地分赛区的“海选”是同步进行的,有点“并行”的意思。

        在算法设计中,也可以引入分而治之的策略,称为分治算法。分治算法的本质就是将一个大规模的问题分解为若干规模较小的子问题,分而治之。

分治算法要素

(1)原问题可分解为若干规模较小的相同子问题。

(2)子问题相互独立。

(3)子问题的解可以合并为原问题的解。

分治算法秘籍

(1)分解:将想要解决的问题分解为若干规模较小、相互独立、与原问题形式相同的子问题。

(2)治理:求解各个子问题。由于各个子问题与原问题形式相同,知识规模较小而已,因此当子问题划分的足够小时,就可以使用较简单的方法来解决。

(3)合并:按原问题的要求,将子问题的解逐层合并,构成原问题的解。

二分搜索

算法题目

        某大型娱乐节目在玩猜数字游戏:主持人在女嘉宾的手心写一个10以内的整数,让女嘉宾的老公猜主持人写的数字是几,女嘉宾只能提示大了或小了,并且只有3次机会。

问题分析

        从问题描述看,如果是n个数,那么最坏的情况需要猜分搜索n次才能成功。其实完全没必要一个数一个数地猜,因为这些数是有序的。可以使用二分搜索策略,每次和中间的元素做比较。如果比中间元素小,就在前半部分查找;如果比中间元间素大,就在后半部分查找。

算法步骤

        一维 数组S[ ]用于存储有序序列,变量low 和high分别表示查找范围的下界和上界,middle 表示查找范围的中间位置,x为特定的查找元素。

(1)初始化。令low=0、high=n-1, 分别指向有序数组S[ ]中的第一个元素和最后一个元素。

(2) middle=(low+high)/2, 指向查找范围的中间元素。

(3) 如果low ≤ high, 转向步骤(4), 否则算法结束。

(4)如果 x = S[middle] , 则查找成功,算法结束。如果x > S[middle] , 则令low = middle + 1;否则令 high = middle - 1,转向步骤(2)。

完美图解

        在有序序列 (5,8. 15, 17. 25, 30. 34, 39, 45,52, 60) 中查找元素17的详细过程如下。

 (1) 确定合适的数据结构。用一维数组S[ ]存储该有序序列,x = 17, 如下图所示。

【趣学算法】Day4 分治算法——二分搜索

(2) 初始化。令low = 0、high = 10, 计算 middle=(low+high)/2=5 , 如下图所示。
【趣学算法】Day4 分治算法——二分搜索
(3) 将 x 与 S[middle] 做比较。S[middle] = 30, x<S[middle],令high = middle-1,在序列的前半部分查找,搜索范围缩小到子问题S[0..middle-1] , 如下图所示。
【趣学算法】Day4 分治算法——二分搜索
(4) 计算 middle = (low+high) / 2 = 2,如下图所示。
【趣学算法】Day4 分治算法——二分搜索
(5) 将x 与 S[middle]做比较。S[middle]=15, x>S[middle], 令low = middle+1,在序列的后半部分查找,搜索范围缩小到子问题S[midde] +1..high],如下图所示。
【趣学算法】Day4 分治算法——二分搜索
(6) 计算 midde=(low+high)/2=3,如下图所示。 

【趣学算法】Day4 分治算法——二分搜索 

(7)将 x 与 S[middle]做比较。x = S[middle] = 17,查找成功,算法结束。

算法详解

        下面使用BinarySearch(int s[ ] , int n , int x)函数实现二分搜索,其中s[ ]为有序数组,n为元素个数,x 为特定的查找元素。首先,令low指向有序数组的第一个元素,同时令high 指向有序数组的最后一个元素。如果 low <= high,则令 middle = (low + high) / 2,也就是令 middle 指向查找范围的中间元素。如果x = S[middle],则查找成功,返回元素的下标。如果x > S[middle],则令low = middle+1,在后半部分搜索;否则令high = middle -1, 在前半部分搜索。
        一般情况下,如果low和high的数值不大,可以采用 middle=(low+high)/2 或者 middle = (low + high) >> 1。如果low和high的数值特别大,为避免low+high溢出,可以采用 middle = low+(high-low)/2。

 

int BinarySearch(int s[], int n, int x) { //二分搜索
    int low = 0, high = n - 1;
    //low 指向有序数组的第一个元素,high 指向有序数组的最后一个元素
    while(low <= high) {
        int middle = (low + high) / 2;
        //middle 指向查找范围的中间元素
        if(x == s[middle]) { //查找成功
            return middle;
        } else if(x > s[middle]) { 
            //x 大于中间元素,在前半部分查找
            low = middle + 1;
            } else {
                //x 小于中间元素,在后半部分查找
                high = middle - 1;
            }
    }
    return -1;
}

 算法分析

 (1)时间复杂度:

        sort 排序函数的时间复杂度为 O(nlogn),如果数列本身有序,那么这部分不用考虑。二分查找算法的时间复杂的怎么计算呢?如果用 T(n) 表示 n 个有序元素的二分查找算法的时间复杂度,那么

        1)当 n = 1 时,需要进行一次比较,T(n) = O(1)。

        2)当 n > 1 时,需要将特定元素和中间元素做比较,时间复杂度为 O(1)。如果比较不成功,则需要在前半部分或后半部分查找,问题的规模缩小了一半,时间复杂度变为 T(n / 2)。

当 n = 1 时,T(n) = O(1);当 n > 1 时,T(n) = T(n / 2) + O(1)。

        3)当 n > 1 时,可以进行递归求解。

        T(n) = T(n / 2) + O(1)

                = T(n / 2 * 2) + 2O(1)

                = T(n / 2 * 2 * 2) + 3O(1)

                =……

                = T(n / 2 的x次方) + xO(1)

递归最终的数据规模为1,也就是说,n / 2 的x次方 = 1。由于 n = 2 的x次方,因此 x = logn。

二分查找算法的时间复杂度为O(logn)

(2)空间复杂度:

        辅助空间是一些变量,它们是常数阶的,因此空间复杂度为O(1)。

【趣学算法】Day4 分治算法——二分搜索文章来源地址https://www.toymoban.com/news/detail-467198.html

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

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

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

相关文章

  • 算法训练day4:栈与队列

    那么我这里再列出四个关于栈的问题,大家可以思考一下。以下是以C++为例,使用其他编程语言的同学也对应思考一下,自己使用的编程语言里栈和队列是什么样的。 C++中stack 是容器么? 我们使用的stack是属于哪个版本的STL? 我们使用的STL中stack是如何实现的? stack 提供迭

    2024年02月01日
    浏览(35)
  • 算法打卡|Day4 链表part02

    今日任务 ● 24. 两两交换链表中的节点 ● 19.删除链表的倒数第N个节点 ● 面试题 02.07. 链表相交 ● 142.环形链表II 目录 Day4 链表part02 Problem: 24. 两两交换链表中的节点 思路 解题方法 Code Code Problem: 19. 删除链表的倒数第 N 个结点 思路 解题方法 Code Problem: 面试题 02.07. 链表相交

    2024年02月08日
    浏览(43)
  • 代码随想录算法训练day4 | 链表

    目录 24. 两两交换链表节点 19. 删除链表倒数第n个节点 方法一:普通写法 方法二:双指针法 面试题:找链表相交节点 142. 判断环形链表 虚拟头节点的本质意义在于减少了特殊情况的处理。不用判断该节点是否在链表的第一位。 定义快慢两个指针。 fast先走n步,再让fast和s

    2024年02月04日
    浏览(61)
  • 数据结构与算法学习(day4)——解决实际问题

    在本章的学习此前,需要复习前三章的内容,每个算法都动手敲一遍解题。宁愿学慢一点,也要对每个算法掌握基本的理解! 前面我们学习了简化版桶排序、冒泡排序和快速排序三种算法,今天我们来实践一下前面的三种算法。 本章的学习目标: (1)回顾三个算法的基本原

    2024年02月09日
    浏览(54)
  • 【算法基础:搜索与图论】3.6 二分图(染色法判定二分图&匈牙利算法)

    https://oi-wiki.org/graph/bi-graph/ 二分图是图论中的一个概念, 它的所有节点可以被分为两个独立的集合,每个边的两个端点分别来自这两个不同的集合 。 换句话说, 二分图中不存在连接同一集合内两个节点的边 。 如何判断一个图是二分图? 当且仅当图中不含奇数环 。(奇数

    2024年02月16日
    浏览(42)
  • 算法刷题营【Day1】:: 704.二分查找:二分法详谈与相关刷题

    本内容是笔者结合《代码随想录》总结所得,记录学习过程,分享知识! 目录: 1. 开篇例题:704. 二分查找 2. 题解参考(模板写法) - - 2.1 方法一:左闭右闭写法 - - 2.2 方法二:左闭右开写法 3. 模板解释:左闭右闭 - - 3.1 区间划定 - - 3.2 left 、right 移动问题 - - 3.3 循环条件

    2024年02月04日
    浏览(45)
  • 算法刷题Day1 二分查找+移除元素

    代码随想录-数组-1.数组理论基础 数组是存放在 连续内存空间 上的 相同类型 数据的 集合 优点:常数时间复杂度访问元素 缺点: 在删除或者增添元素的时候,就难免要移动其他元素的地址 ,时间复杂度为O(n) 代码随想录-数组-2.二分查找 前提条件 二分查找前提条件: 数组

    2024年02月10日
    浏览(52)
  • 代码随想录算法练习Day1:二分查找

    题目链接:704. 二分查找 卡哥视频讲解:手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode:704. 二分查找 二分法概述: 二分法(Binary Search)是一种在有序数组或列表中查找目标元素的算法。 二分法使用前提 : 有序数组或列表 :二分法要求在查找的数据结

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

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

    2024年01月17日
    浏览(57)
  • 蓝桥杯备赛 day 2 —— 二分算法(C/C++,零基础,配图)

    目录 🌈前言: 📁 二分的概念 📁 整数二分 📁 二分的模板 📁 习题 📁 总结          这篇文章主要是准备蓝桥杯竞赛同学所写,为你更好准备蓝桥杯比赛涉及的算法知识点。不知道你是否苦恼于不知算法从何学起,苦恼于网上资料稀少,或者复杂难懂,这篇文章就是

    2024年01月18日
    浏览(54)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包