二分法思维导图

U425500912

2023-04-08

浏览量: 13

二分法

二分法

C语言

计算机

编程

二分法知识梳理

树图思维导图提供《二分法》在线思维导图免费制作，点击“编辑”按钮，可对《二分法》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：2ebb94c4458f88550bc9d2c84d888036

思维导图大纲

相关思维导图模版

二分法思维导图模板大纲

二分法

算法

当数据量很大适宜采用该方法。采用二分法查找时，数据需是排好序的。

基本思想

假设数据是按升序排序的，对于给定值key，从序列的中间位置k开始比较，如果当前位置arr[k]值等于key，则查找成功；若key小于当前位置值arr[k]，则在数列的前半段中查找,arr[low,mid-1]；若key大于当前位置值arr[k]，则在数列的后半段中继续查找arr[mid+1,high]，直到找到为止,时间复杂度:O(log(n))。

1245：不重复地输出数

思路

可以用for循环输出，输出当前数的时候，判断下是否和上一个数相等，不相等的时候输出

1244:和为给定数

思路

定义一个一维数组，输入数据后，按从小到大排序，再查找是否有符合要求的两个数。

1235：输出前k大的数

思路

按照快速排序的思想，把数组前k大的数放到数组末尾。然后在对数组末尾k个元素做排序再输出该部分元素。

1237：求排列的逆序数

思路

这个题其实就考察”归并“排序，程序也不难，就提一点：注意等号和边界。

C++语言中的二分法查找

算法

当数据量很大适宜采用该方法。采用二分法查找时，数据需是排好序的。

基本思想

假设数据是按升序排序的，对于给定值x，从序列的中间位置开始比较，如果当前位置值等于x，则查找成功；若x小于当前位置值，则在数列的前半段中查找；若x大于当前位置值则在数列的后半段中继续查找，直到找到为止。

二分法是什么？

二分法通常又叫二分查找，一般用于查找一个有序数组中的某个值的位置或者给定的特定值的插入位置；相比把整个数组遍历一次的O（n)复杂度，二分查找可以把复杂度降低到O（logn); 二分查找的基础概念在这里就不再赘述，本文主要记录二分法的基本情况使用和采用二分思路来求解的一些问题。

二分法在什么情况下使用

二分法一定是建立在元素有序的前提下的(或数据具有二段性）；所以看到题目中出现有序数组等词时，并且要求我们查找某个值或者给一个值求插入位置，或者判断其中是否存在某个值或者利用二分思路求最大最小值等；这些都可以使用二分法；

二分法需要注意的细节

二分法的思路很简单，无非就是每次根据中值判断，然后缩减区间到原来的一半；二分法最容易出错的地方在于边界和细节处理，大体逻辑并不难写出，我们往往死在细节处理上。

在二分查找的过程中，保持不变量；这也就是循环不变量。

二分法的边界模板分为两种

一种是左闭右闭的区间写法[left,right]： while(left<=right) left的改变为left=mid+1,right的改变为right=mid-1;

一种是左闭右开的区间写法[left,right) : while(left<right) left的改变为left=mid+1,right的改变为right=mid;

实际应用

写法一：区间左闭右闭【left,right】

写法二：区间左闭右开【left，right）

总结

二分查找是一个时间效率极高的算法，尤其是面对大量的数据时，其查找效率是极高，时间复杂度是log(n)。主要思想就是不断的对半折叠，每次查找都能除去一半的数据量，直到最后将所有不符合条件的结果都去除，只剩下一个符合条件的结果。

二分法的时间复杂度是log(n)，但log(n)为什么效率这么高呢？接下来我举个例子来描述一下：

我们都听说过指数爆炸，何为指数爆炸，就是在指数不断增加的情况下，其数值的上升速度不断增加，上升速率可以迅速的接近增无穷。

同样也有这样一个理论去描述指数爆炸的威力：那就是一个乒乓球每秒钟翻一倍，五分钟可以填满整个宇宙。

而我们二分法就相当于上升的逆转，一个每秒钟翻一倍的乒乓球，五分钟就可以堆满整个宇宙，反之，堆满整个宇宙的乒乓球，每秒钟减少一半，五分钟后就只剩一个。

二分法的套路

使用二分法，我们要按照一下两个步骤：

1.我们要确定一个区间[L，R]

2.我们要找到一个性质，并且该性质满足一下两点： ①满足二段性 ②答案是二段性的分界点。

查看更多

二分法查找思维导图

树图思维导图提供《二分法查找》在线思维导图免费制作，点击“编辑”按钮，可对《二分法查找》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：97899d0f520dda5adc3bf1f11af9952a

二分法查找

二分法思维导图

树图思维导图提供《二分法》在线思维导图免费制作，点击“编辑”按钮，可对《二分法》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：e81c466e42c874c1d66362f520431012

二分法

思维导图模板

行业/职业模板

正文

相似思维导图模版

主机安全防御思维导图

2024-11-13 11:28:28

主机安全防御

人机料环鱼骨图思维导图

2024-07-29 16:27:50

人机料环鱼骨图

项目二旅游简史思维脑图思维导图

2024-01-22 19:09:23

项目二旅游简史思维脑图

电工电子基础脑图思维导图

2023-12-04 02:00:36

电工电子基础脑图

环境设计各业务版块流程图思维导图

2024-11-13 10:05:12

环境设计各业务版块流程图

决策和决策过程思维导图

2024-03-24 21:17:27

决策和决策过程

思维导图模版推荐

面试自我介绍的内容思维导图

2023-04-08 18:15:13

面试自我介绍的内容

学生成绩表思维导图

2023-04-08 18:18:29

学生成绩表

如何在面试自我介绍中叙述求职动机？思维导图

2023-04-08 18:25:50

如何在面试自我介绍中叙述求职动机？

血液透析导管连接处断开鱼骨图分析思维导图

2023-04-08 18:08:11

血液透析导管连接处断开鱼骨图分析

面试自我介绍的原因思维导图

2023-04-08 17:57:42

面试自我介绍的原因

数学分析思维导图

2023-04-08 17:22:52

数学分析

首页

我的文件

我的团队

个人中心