【算法】二分法 ① ( 二分法基本原理简介 | 二分法与哈希表对比 | 常见算法对应的时间复杂度 )

文章目录

• ​​一、二分法基本原理简介​​

• ​​1、二分法与哈希表对比​​
• ​​2、二分法具体步骤​​

• ​​二、常见算法对应的时间复杂度​​

一、二分法基本原理简介

二分法算法 是 基于 数组 数据结构 的 ;

数组 中的元素 是 已经 排序好的

1、二分法与哈希表对比

哈希表时间复杂度 : 如果将所有元素 放在 哈希表 中 , 从 哈希表 中查询某个元素是否存在 , 其 时间复杂度为 , 使用哈希表的前提是 所有的数据 都要读取到内存中 ;

哈希表的缺陷 : 如果 数组集合 的元素数量很大 , 如几十万个元素 , 则无法将其完整的读取到内存中 , 此时就无法使用哈希表进行查询了 ;

二分法 与 哈希表法 对比 :

• 算法灵活性 : 使用二分法 查询数组中的数据 , 数组的数据不仅仅局限于内存中 , 可以 存放在硬盘 , 网络 等介质中
• 时间复杂度 : 二分法 的 时间复杂度 是 , 其比 哈希表 HashSet 的 时间复杂度 要高 , 但是 二分法 实现非常灵活 ;

2、二分法具体步骤

二分法步骤 :

• 首先 , 确定 数组 的查找区间 , 一般是 从第 0 个元素 到 最后一个元素 , 开始元素索引设置为 start 变量 , 结束元素索引设置为 end 变量 ;
• 然后 , 找到 start 索引 和 end 索引 的中间值 索引 , 将 该中间值索引的元素 与 查找目标值 进行对比 ;

• 如果 中心元素 = 目标值 , 直接返回该索引值 ;
• 如果 中心元素 < 目标值 , 则需要去 该查找区间的 右侧继续查找 , 经过该操作查找区间被缩小了一半 ;
• 如果 中心元素 > 目标值 , 则需要去 该查找区间的 左侧继续查找 , 经过该操作查找区间被缩小了一半 ;

• 最后 , 如果上述遍历出现 start >= end , 则说明该数组中没有目标值 ;

二、常见算法对应的时间复杂度

常见算法对应的时间复杂度 : 时间复杂度从小到大进行排序 ;

• : 位运算 , 哈希表查询
• : 二分法 , 快速幂算法 , 辗转相除法 , 倍增法 ;
• : 枚举法 ,双指针算法 ;
• : 快速排序 , 归并排序 , 堆排序 ;
• : 枚举法 , 动态规划 ;
• : 枚举法 , 动态规划 ;
• : 组合相关的搜索问题 ;
• : 排列相关的搜索问题 ;

算法示例 : 判定数组中是否存在某个 目标值 元素 , 如何进行优化 ;

• 最差算法 : 如果每次都 扫描一遍数组 , 查询目标值是否存在 , 该操作的 时间复杂度是 , 也就是数组如果有 个元素 , 则最坏情况需要遍历
• 优化算法 : 对数组进行 排序 , 然后使用 二分法 进行查找 , 则每次查询的 时间复杂度是
• 最优算法 : 将数组元素存入 哈希表 , 每次查询的 时间复杂度是