当前位置: 首页 > news >正文

【C++习题】17.二分查找算法_二分查找

文章目录

    • 二分查找算法简介
    • 题目链接:
    • 题目描述:
    • 解法
    • C 算法代码:
    • 图解
    • 总结朴素二分模板


二分查找算法简介

  1. 特点:

    二分查找算法,是最恶心,细节最多,最容易写出死循环的算法。(而且非常难调试)

    不过如果真的掌握了二分算法后,会觉得这个是最简单的算法。

  2. 学习中的侧重点:

  • 算法原理:

    一开始会觉得只有数组有序的情况才能使用二分算法

    但是学到后面,会发现就算无序,只要有规律也可以使用二分算法

  • 模板:

    不要死记硬背,需要理解背后的原理,做到理解后再记忆。

  • 会讲3个模板

    1. 朴素的二分模板
    2. 查找左边界的二分模板
    3. 查找右边界的二分模板

    3个模板加起来不超过20行,可以解决 99.99%的二分题,但不能只背模板。

下面的一题会讲到第一个模板,后一题会讲第二第三个模板。

朴素的二分模板,朴素意味着简单,只有一些非常简单的二分题才用到。

查找左边界的二分模板和查找右边界的二分模板是万能的,也就是朴素模板可以解决的也可以用另外两个解决,不过细节很多。


题目链接:

leetcode 704.二分查找


题目描述:

1be6c7f089504a35d0b597130220a99a


解法

暴力解法:

遍历一遍,时间复杂度O(n)

例如:[1,2,3,4,5,6,7,8],t=5

比如44t小,那么它前面的比4还小,那么全比t小,可以把44之前的数全干掉。

同理,66后面的数也一样可以干掉。

总的来说就是,随便找个端点,只要不是目标值,那么它的一侧可以全部干掉。

1c7ba1675a5cbc7805fffeb318dda1d6

总结来说就是:二段性

就是当我们发现一个规律,然后根据这个规律选取某一个点能把这个数组分成两部分,然后根据规律可以有选择的舍去一部分,进而在另一部分里面继续查找的时候,就可以使用二分查找算法。

注意上面的描述,不管有序无序,只要有二段性都可以使用二分算法。

对于端点的选择,我们可以选择1/2处,1/3处,1/4处等等。我们的目的是找到二段性。

d8950a8df31ada3f3582a16b9524dfb0

所以端点的选择比较多,但是我们一般选1/2的点。在概率学里面是求数学期望。

就像1/3处的点,虽然可能直接把2/3的部分抹除,但是也可能只抹除了1/3

在这么多的端点的划分里面,选择中间这个点的时间复杂度是最好的。

我们可以定义一个left指针,right指针和mid指针

2b69be9afa2c4c0ef9e9f6cb5a26f6e1

3步就是朴素二分算法的核心了。

细节问题:

  1. 循环结束的条件是什么?

    left>right的时候结束循环

    left<=right的时候一直循环

  2. 为什么是正确的?

    通过二段性达到和暴力解法一样的排除作用

  3. 为什么时间复杂度快?

    log2n


C 算法代码:

int search(int* nums, int numsSize, int target)
{// 初始化 left 与 right 指针int left = 0, right = numsSize - 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;}// 如果程序走到这里,说明没有找到目标值,返回 -1return -1;
}

图解

例如:[1,2,3,4,5,6,7,8],t=5

  1. left = 0, right =7

    left <= right进入循环

    mid=0+(7-0)/2=3

    feda6fb805921b2070f1e0d230213699

    nums[mid]=4<t

    满足else条件,执行left = mid + 1=4

  2. left = 4, right =7

    left <= right进入循环

    mid=4+(7-4)/2=5

    40df4dd4ef03864fbc9c6b0ff8aa759f

    nums[mid]=6>t

    满足nums[mid] > target条件,执行right = mid - 1=4

  3. left = 4, right =4

    left <= right进入循环

    mid=4+(4-4)/2=4

    335900edd72646f1db635b92cf5efd11

    满足nums[mid] == target)条件,执行return mid;

9f6db2e718b4632e413f5d6b27903163

  1. 程序结束。

总结朴素二分模板

while(left <= right){int mid = left + (right - left) / 2;//int mid = left + (right - left + 1) / 2;//这两个在朴素版本作用一样if(......)left = mid + 1;else if(......)right = mid - 1;elsereturn ......;
}
http://www.lryc.cn/news/493397.html

相关文章:

  • Spring Boot英语知识网站:架构与开发
  • Unity ShaderLab 实现网格爆炸
  • 2024/11/28学习日志
  • 在shardingsphere执行存储过程
  • 1.文件目录操作
  • Vue单页面应用和多页面应用
  • Lombok :简化 Java 编程的得力工具
  • AIGC引领金融大模型革命:未来已来
  • DBA面试题-1
  • 用go语言写一个小服务
  • 亚马逊开发视频人工智能模型,The Information 报道
  • WordCloud参数的用法:
  • qml调用c++类内函数的三种方法
  • NLP任务四大范式的进阶历程:从传统TF-IDF到Prompt-Tuning(提示词微调)
  • GAMES101:现代计算机图形学入门-笔记-09
  • 【Db First】.NET开源 ORM 框架 SqlSugar 系列
  • MySQL聚合查询分组查询联合查询
  • 告别照相馆!使用AI证件照工具HivisionIDPhotos打造在线证件照制作软件
  • 通信原理第三次实验
  • 【halcon】Metrology工具系列之 get_metrology_object_result_contour
  • A052-基于SpringBoot的酒店管理系统
  • NLP信息抽取大总结:三大任务(带Prompt模板)
  • python常见问题-pycharm无法导入三方库
  • 迅为RK3588开发板Android系统开发笔记-使用ADB工具
  • 什么是分布式数据库?
  • Leetcode 3363. Find the Maximum Number of Fruits Collected
  • 【数据仓库 | Data Warehouse】数据仓库的四大特性
  • springboot配置多数据源mysql+TDengine保姆级教程
  • dns实验2:反向解析
  • ZooKeeper 基础知识总结