day-14-二分查找（下）

发表于2024-07-26|更新于2024-07-26|数据结构与算法学习笔记

|总字数:169|阅读时长:1分钟|浏览量:

一、二分查找的变形问题

变体一：查找第一个值等于给定值的元素

对于我们做工程开发的人来说，代码易读懂、没 Bug，其实更重要。

变体二：查找最后一个值等于给定值的元素

变体三：查找第一个大于等于给定值的元素

变体四：查找最后一个小于等于给定值的元素

二、小结

变体的二分查找算法写起来非常烧脑，很容易因为细节处理不好而产生 Bug，这些容易出错的细节有：终止条件、区间上下界更新方法、返回值选择。

文章作者: 张晓风

文章链接: https://zhangyuliang1994.github.io/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0-day-14-%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE%EF%BC%88%E4%B8%8B%EF%BC%89/

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源张晓风的博客！

数据结构与算法

相关推荐

day-1-复杂度分析（上）

一、为什么需要复杂度分析1.1 事后统计法的局限性测试结果非常依赖测试环境测试结果受数据规模的影响很大 1.2 大 O 复杂度表示法大 O 时间复杂度表示法表示代码执行时间随数据规模增长的变化趋势，也叫渐进时间复杂度，简称时间复杂度。二、时间复杂度分析方法2.1 只关注循环执行次数最多的一段代码2.2 加法法则：总复杂度等于量级最大的那段代码的复杂度2.3 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积三、几种常见时间复杂度分析 3.1 非多项式量级非多项式量级只有两个：O(2的n次方)和O(n!) 3.2 多项式量级a) O(1)一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是O(1)。 b) O(logn)、O(nlogn)对数阶时间复杂度非常常见，同时也是最难分析的一种时间复杂度。归并排序、快速排序的时间复杂度都是O(nlogn)。 c) O(m + n)、O(m * n)T1(m) + T2(n) = O(f(m) + g(n))T1(m) * T2(n) = O(f(m) * ...

day-10-排序（下）

一、归并排序的原理归并排序的核心思想：如果要排序一个数组，先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。归并排序使用的就是分治思想。分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。分治是一种解决问题的处理思想，递归是一种编程技巧二、快速排序的原理快排的思想是这样的：如果要排序数组中下标从 p 到 r 之间的一组数据，我们选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。我们遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。经过这一步骤之后，数组 p 到 r 之间的数据就被分成了三个部分，前面 p 到 q-1 之间都是小于 pivot 的，中间是 pivot，后面的 q+1 到 r 之间是大于 pivot...

day-11-线性排序

一、桶排序核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。桶排序比较适合用在外部排序中。二、计数排序计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。三、基数排序基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果 a 数据的高位比 b 数据大，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到 O(n)...

day-12-排序优化

一、如何选择合适的排序算法如果对小规模数据进行排序，可以选择时间复杂度是 O(n2) 的算法；如果对大规模数据进行排序，时间复杂度是 O(nlogn) 的算法更加高效。所以，为了兼顾任意规模数据的排序，一般都会首选时间复杂度是 O(nlogn) 的排序算法来实现排序函数。 O(n2) 时间复杂度出现的主要原因还是因为我们分区点选得不够合理。最理想的分区点是：被分区点分开的两个分区中，数据的数量差不多。 1.1 三数取中法我们从区间的首、尾、中间，分别取出一个数，然后对比大小，取这 3 个数的中间值作为分区点。这样每间隔某个固定的长度，取数据出来比较，将中间值作为分区点的分区算法，肯定要比单纯取某一个数据更好。 1.2 随机法随机法就是每次从要排序的区间中，随机选择一个元素作为分区点。这种方法并不能保证每次分区点都选的比较好，但是从概率的角度来看，也不大可能会出现每次分区点都选得很差的情况，所以平均情况下，这样选的分区点是比较好的。二、小结我们大部分排序函数都是采用 O(nlogn)...

day-13-二分查找（上）

一、二分思想二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为...

day-2-复杂度分析（下）

一、最好、最坏情况时间复杂度最好情况时间复杂度：在最理想的情况下，执行这段代码的时间复杂度。最坏情况时间复杂度：在最糟糕的情况下，执行这段代码的时间复杂度。二、平均情况时间复杂度平均时间复杂度：也叫加权平均时间复杂度，在大多数情况下，我们并不需要区分最好、最坏、平均情况时间复杂度，我们使用一个复杂度就可以满足需求了。只有同一块代码在不同的情况下，时间复杂度有量级的差距，我们才会使用这三种复杂度表示法来区分。三、均摊时间复杂度对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候，我们就可以将这一组操作放在一块儿分析，看是否能将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上。而且，在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度。均摊时间复杂度就是一种特殊的平均时间复杂度，没必要花太多精力区分它们。

评论