首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

为什么当数组按降序排序时,二进制搜索方法不起作用?

当数组按降序排序时,二进制搜索方法不起作用的原因是二进制搜索方法是基于数组有序的前提下进行的。在升序排序的数组中,二进制搜索方法可以通过比较目标值与数组中间元素的大小关系,从而确定目标值在数组的哪个部分,然后继续在该部分进行搜索,以此类推,直到找到目标值或确定目标值不存在。

然而,当数组按降序排序时,二进制搜索方法无法正确确定目标值在数组的哪个部分。因为在降序排序的数组中,中间元素的值可能比目标值大,但实际上目标值可能在中间元素的左边。这导致二进制搜索方法无法准确地确定目标值所在的部分,从而无法正确地进行搜索。

为了解决这个问题,可以通过修改二进制搜索方法的比较逻辑,使其适应降序排序的数组。具体做法是,在比较目标值与中间元素大小时,将比较操作反转,即如果目标值小于中间元素,则继续在中间元素的右边进行搜索,反之则在左边进行搜索。这样可以保证在降序排序的数组中仍然能够正确地确定目标值所在的部分,从而实现有效的搜索。

总结起来,当数组按降序排序时,二进制搜索方法不起作用的原因是无法准确地确定目标值所在的部分。为了解决这个问题,可以通过修改比较逻辑来适应降序排序的数组。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

数据结构——排序

(也就是说我们按照规律可能排升序,也有可能排降序) 在我们的生活中,处处都有排序的影子~比如世界五百强,中国内地大学排名,学生成绩排名……这些都是排序的运用,程序员们就需要使用排序来解决问题~ 这里给出常见的排序算法...我们可以看到有两层循环,外层循环次数为n,内层循环次数当我们排序的数组是降序要排序成升序时,那么内层循环次数依次为1、 2、3……n,根据时间复杂度表示法的规则,取最坏的情况,那么时间复杂度就为O(N^...2),不清楚的时间复杂度表示方法的记得看看这一篇博客哦~数据结构——复杂度 希尔排序 既然直接插入排序时间复杂度为O(N^2),那么有没有什么方法可以优化一下它呢?...当 gap > 1 时都是预排序,目的是让数组更接近于有序。 当 gap == 1 时,数组已经接近有序, 这样就会很快。整体来看,可以达到优化的效果。...)是指利用堆积树(堆)这种数据结构所设计的⼀种排序算法,排升序要建大堆,排降序建小堆~这里我们给出代码~有疑问的可以再看看这一篇博客~数据结构——二叉树 //向下调整数据 AdjustDown(HPDataType

6410
  • 【初阶数据结构篇】插入、希尔、选择、堆排序介绍(上篇)

    插入、希尔、选择、堆排序 前言 本篇以排升序为例 代码位置 gitee 排序方法 常见排序算法 本篇介绍前四种,在之后博客中会讲到交换排序和归并排序以及计数排序 插入排序 直接插入排序 基本思想...= arr[end]; end--; } else { break; } } arr[end + 1] = tmp; } } 时间复杂度分析: 最坏情况:数组降序排列...特别是当数组为降序,我们要排升序,此时数组的相对无序程度达到了最大,时间复杂度也到了最大 所以我们有没有办法对这样一种情况进行优化呢?...为n/3时,移动总数为: n 当gap为n/9时,移动总数为: 4n 最后⼀趟,数组已经已基本有序了,gap=1即直接插⼊排序,移动次数就是n 通过以上的分析,可以画出这样的曲线图: 因此,希尔排序在最初和最后的排序的次数都为...需要注意的是排升序要建⼤堆,排降序建⼩堆。 在堆的应用(堆排序与Top-K问题)已经讲过了此方法,这里就不赘述了。

    9710

    【初阶数据结构篇】插入、希尔、选择、堆排序

    插入排序 1.1 直接插入排序 基本思想 直接插⼊排序是⼀种简单的插⼊排序法,其基本思想是:把待排序的记录按其关键码值的⼤⼩逐个插⼊到⼀个已经排好序的有序序列中,直到所有的记录插⼊完为⽌,得到⼀个新的有序序列...= arr[end]; end--; } else { break; } } arr[end + 1] = tmp; } } 时间复杂度分析: 最坏情况:数组降序排列...特别是当数组为降序,我们要排升序,此时数组的相对无序程度达到了最大,时间复杂度也到了最大. 希尔排序法⼜称缩⼩增量法。...,再将数组分成各组,进⾏插⼊排序,当gap=1时,就相当于 直接插⼊排序。...//避免maxi begini都在同一个位置,begin和mini交换之后,maxi数据变成了最小的数据 if (maxi == begin) { maxi = mini; } 为什么会造成这样

    6610

    数据结构与算法之二 排序

    节省时间和高效搜索数据的简单解决方案是排序。 排序 是按照某些预定义的顺序或序列排列数据的过程。 此顺序可以是升序 或降序。...最佳用例效率: 当列表已经被排序时产生最佳用例。 在这种情况下,您必须在每个通道中仅做一次比较。 在n– 1次通道中,您将需要做n– 1次比较。 插入排序的最佳用例效率是O(n)阶的。...最糟用例效率: 当列表按反向顺序排序时产生最糟用例效率。 在这种情况下,您需要在第1个通道中做1次比较,在第二个通道中做2次比较,在第3个通道中做3次比较,在第n– 1 个通道中做n – 1次比较。...为什么? 记录是以随意顺序存储的。     答案: 当列表部分排序时,插入排序提供了比泡泡排序和选择排序更好的有效。因此David应使用插入排序算法。...当元素已经处于排 序阶,则插入排序需要进行极少比较。 如果需要排序的列表几乎已经排序,则插入排序比冒泡排序和选择排序更有效率。 通过比较按若干位置的距离分隔的元素,壳排序改善了插入排序 。

    11510

    大厂面试系列(七):数据结构与算法等

    按出现频次的高低输出所有的数字 给定一个乱序数组,求数组内最大连续的数; 无序数组找第k大的数 给一个数组,和k,求数组中的哪两个数之和为k,除了双层for循环和字典的方式还能用什么方式实现; 查找 写二分查找算法...用二分法查找一个长度为18的,排好的线性表,当查找不成功时,最多需要比较多少次 排序 快排怎么实现的,快速排序(包括算法步骤、平均算法复杂度、最好和最坏的情形) 5亿整数的大文件,怎么排?...排序算法,介绍一下快速排序,快速排序时间复杂度,是不是稳定排序,介绍几种你所知道的稳定排序算法 10亿个数选最大的K个,用什么方法,复杂度多少 说一下冒泡排序的原理 请对3个有序数组进行归并排序 树 AVL...给一个二叉树和一个目标值,找到和等于这个值的所有路径 B和B+树,B+树的搜索次数、为什么不用二叉树。 红黑树最差旋转几次 给定一棵二叉树,找到两个节点的最近公共父节点(LCA)。...为什么会栈溢出?python函数中的临时变量存在哪?那很深的时候,用循环会怎样呢?为什么不会栈溢出?

    1.2K20

    每个程序员都应该知道的算法

    ---- 线性搜索 在计算机科学中,线性搜索或顺序搜索是一种用于在列表中查找元素的方法。它顺序检查列表中的每个元素,直到找到匹配项或搜索了整个列表。...在线性搜索中,我们从列表的第一个元素到最后一个按顺序依次搜索列表中的目标元素。...最佳情况:目标值位于列表的第一位 最坏的情况:目标值是列表的最后位置 何时使用: 列表未排序时 当清单很小的时候 ---- 二进制搜索 在计算机科学中,二进制搜索(也称为半间隔搜索,对数搜索或二进制chop...二进制搜索将目标值与数组的中间元素进行比较。如果它们不相等,则消除目标不能位于其中的那一半,并在剩余的一半上继续搜索,再次使中间元素与目标值进行比较。...最佳情况:目标值位于列表的中间位置 最坏的情况:目标值位于列表的第一个或最后一个位置 何时使用: 列表排序时 当清单很大时 ---- 深度优先搜索(DFS) 深度优先搜索(DFS)是用于遍历或搜索树或图形数据结构的算法

    55020

    LeetCode-面试题40-最小的k个数

    示例2: 输入:arr = [0,1,2,1], k = 1 输出:[0] 限制: 0 <= k <= arr.length <= 10000 0 <= arr[i] <= 10000 # 解题思路 方法...1、快排+选择: 基于之前快速排序的代码实现,现在加了几个条件,如下: 每快排切分1次,找到切分点,比较切分点和k的关系 如果相等则意味着,切分点左边的数字已经是最小数组集合,直接返回 如果k小于m说明需要在左子数组进行搜索...如果k大于m说明需要在右子数组进行搜索 方法2、最大堆: 使用Java的优先级队列PriorityQueue,实现最大堆 当队列不足k个的时候,传入一个元素 当队列大于k个的时候,判断下一个元素是否小于堆顶...,直接返回 if(k==m){ return; } // 如果k小于m说明需要在左子数组进行搜索 else if(...k<m){ quickSort(list,left,m-1,k); } // 如果k大于m说明需要在右子数组进行搜索 else{

    19710

    MySQL 8.0新特性:降序索引

    降序索引可以按向前顺序进行扫描,这样效率更高。当最有效的扫描顺序将某些列的升序与其他列的降序混合时,降序索引还使优化程序可以使用多列索引。...,InnoDB现在可以按降序存储条目,并且当查询中请求降序时,优化器将利用它。...而在MySQL5.7中,由于组成联合索引的c1字段和c2字段都是升序排列的,那么在使用order by c1,c2排序时,MySQL可以对索引进行正向扫描,在使用order by c1 desc,c2...但是需要注意的是,降序索引的引入,只是多提供给我们一种索引的使用方法,它并不能做到赢家通吃,无法适用所有的排序场景。...InnoDB SQL解析器不使用降序索引。对于InnoDB全文搜索,这意味着索引表的FTS_DOC_ID列上所需的索引不能定义为降序索引。 适用于升序索引的所有数据类型也都支持降序索引。

    2.8K40

    *常见排序算法代码实现及特性分析*

    一、直接插入排序 1.基本思想: 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到全部插入完为止,得到一个新的有序序列。...即排序前后相同元素值的前后位置不会改变,代码中的体现就是第2个for循环中的条件“array[j] > val”,相等时并不往后移,故保证了稳定性); (3)平均时间复杂度:O(N^2); (4)最好时间复杂度:O(N),所排数组已经全部有序...,只需进行N次比较; (5)最坏时间复杂度:O(N^2),所排数组是倒序排列,第N个元素需要(N-1)次比较操作和N次移位操作,操作次数总共为N(N-1)/2 + N(N+1)/2,故时间复杂度为O(N...*注:排升序建大根堆,排降序建小根堆 *图解来源:百度图片堆排序图解过程 2.代码实现: 3.特性总结: (1)使用场景:没有特定场景; (2)稳定性:不稳定(交换数据的时候,是父节点和子节点进行比较...logN = N*(logN); (4)空间复杂度:O(N),二路归并时需要开辟额外的数组空间来进行排序,然后有序地搬移回原数组中。

    79700

    为什么快速排序算法效率比较高?

    下面我们用数学方式来推导冒泡排序时间复杂度是如何计算的: 首先冒泡排序是基于比较和交换的,比如我们要对n个数字排序,冒泡排序需要n-1次遍历,比如我们有10个数字,第一趟循环需要比较9次,第二趟循环需要比较...快速排序的理论是找到一个基准数,将大于该数的数字全部放在右边,而小于该数字的全部放在左边,如此将一个大数组一切为二,接着在两个小数组里面也采用同样的方法,找基准,大的放右,小的放左,直到分解到子问题里面只有一个数字...[]a=new int[]{6,1,2,7,9,3,4,5,10,8}; quickSort(a,0,a.length-1); 快速排序快的主要原因是大大减少了比较和交换的次数,因为按基准数切分的两半数组...下面我们来分析下快排的Ο(nlog2n)的时间复杂度如何得来的,假设我们随机取的基准数总是能把整个数组给平均切成2个子数组: 快排的简化版代码如下: quick_sort(n){...当然快排虽然在大多数时候表现很出色,但在一些极端情况下复杂度也会达到O(n^2),比如已经升序拍好的数组,降序排序好的数组,全部重复的数组,当然针对这些case都有优化的方式,重点在于基准数的选择,此外还有两点关于快排的注意事项

    9.6K30

    Pandas Sort:你的 Python 数据排序指南

    现在,您的 DataFrame 按城市条件下测量的平均 MPG 降序排序。MPG 值最高的车辆在第一排。...注意:在 Pandas 中,kind当您对多个列或标签进行排序时会被忽略。 当您对具有相同键的多条记录进行排序时,稳定的排序算法将在排序后保持这些记录的原始顺序。...下一个示例将解释如何指定排序顺序以及为什么注意您使用的列名列表很重要。 按升序按多列排序 要在多个列上对 DataFrame 进行排序,您必须提供一个列名称列表。...按索引降序排序 对于下一个示例,您将按索引按降序对 DataFrame 进行排序。...在这种情况下,按月按升序或降序排列数据是有意义的。 在 Pandas 中排序时处理丢失的数据 通常,现实世界的数据有很多缺陷。

    14.3K00

    算法之排序

    节省时间和高效搜索数据的简单解决方案是排序。 排序是按照某些预定义的顺序或序列排列数据的过程。此顺序可以是升序或降序。...最佳用例效率: 当列表已经被排序时产生最佳用例。 在这种情况下,您必须在每个通道中仅做一次比较。 在n– 1次通道中,您将需要做n– 1次比较。 插入排序的最佳用例效率是O(n)阶的。...最糟用例效率: 当列表按反向顺序排序时产生最糟用例效率。 在这种情况下,您需要在第1个通道中做1次比较,在第二个通道中做2次比较,在第3个通道中做3次比较,在第n– 1 个通道中做n – 1次比较。...为什么? 记录是以随意顺序存储的。 答案: 当列表部分排序时,插入排序提供了比泡泡排序和选择排序更好的有效。因此David应使用插入排序算法。...当元素已经处于排序阶,则插入排序需要进行极少比较。 如果需要排序的列表几乎已经排序,则插入排序比冒泡排序和选择排序更有效率。 通过比较按若干位置的距离分隔的元素,壳排序改善了插入排序。

    8810

    基数排序是什么?

    基数排序是一种很特别的排序方法,它不基于比较和移动进行排序,而基于关键字各位的大小进行排序。基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。...实现方法 最高位优先(Most Significant Digit first)法,简称MSD法:先按k1排序分组,同一组中记录,关键码k1相等,再对各组按k2排序分成子组,之后,对后面的关键码继续这样的排序分组...* 例如,对于数组a={50, 3, 542, 745, 2014, 154, 63, 616}; * (01) 当exp=1表示按照"个位"对数组a进行排序 * (02) 当exp=10...表示按照"十位"对数组a进行排序 * (03) 当exp=100表示按照"百位"对数组a进行排序 */ void count_sort(int a[], int n, int exp) {...当对数组按各位进行排序时,exp=1;按十位进行排序时,exp=10;...

    77820

    程序设计基础课程设计

    学会如何在C语言中实现基本的数组操作和排序算法,如何处理在编程过程中遇到的常见问题。 实验中应注意的问题 冒泡排序实现问题:在实现冒泡排序时,应考虑到应该按照降序(从高到低)排序。...; 4、根据 sort(int a[],int n, char style)函数的 style 参数进行排序,如 style 为‘a’按升序排,style 为’d’按降序排(备注: a:ascending...,用指针实现,输出排序后的成绩单 5、采用指针方法,输入字符串“student score ”,复制该字符串并输出(复制字符串采用库函数或用户自定义函数) (1)任务分析 1.数组元素的访问:使用指针指向数组的首地址...加深了我对指针和数组的理解,掌握了使用指针操作数组元素的方法,并学会了将功能封装进函数进行调用。同时,我们也意识到了在编写程序时需要注意的问题,如错误处理、内存管理、代码的可读性和可维护性等。...实验中应注意的问题 数据结构设计:使用固定大小的数组来存储学生信息,但这限制了系统的可扩展性。当需要添加更多学生时,系统无法处理。

    33920

    【数据结构】——排序之冒泡排序

    冒泡排序的名称来源于排序过程中,较小的数据项会被逐渐“浮”到数组顶部,这个过程就像碳酸饮料中二氧化碳气泡最终会上浮到顶部的现象一样。因此,这种排序算法因其这一特性而得名。...冒泡函数的核心思想就是:两两相邻的元素进行比较,一轮下来最大的或者最小的就会被交换到最后面,每一轮都得到该轮的最值排到后面,如果是升序就得到最大值,降序就是最小值,排n轮直到有序。...2.2进阶版(升序) 进阶实现: 我们发现上述代码即使在排序过程中有序了,该跑size-1趟还是不会少,它才不管你有没有序,我只要跑我的size-1趟就好了,这样就会大大消耗我们的时间,所以我们的想个方法一旦它有序冒泡排序就停下..., sz); for (int i = 0; i < sz; i++) { printf("%d ", arr[i]); } return 0; } 结果如下: 4.冒泡排序时间复杂度分析...时间复杂度往往分析最坏的情况,所以在分析冒泡排序时我们可以当作冒泡了size-1次,假设有n个数,也就是n-1次,每次又两两相比较,第一次比较n-1下,第二次n-2…最后一次1下,将这n-1次加起来就可以知道冒泡排序的时间复杂度啦

    12110

    十大排序算法详解(一)冒泡排序、选择排序、插入排序、快速排序、希尔排序

    也许有人会有疑问“第2趟比较结束后,数组已经有序了,为什么还要进行第3次比较”?...3.3.2 时间复杂度   在插入排序中,当待排序序列是有序时,是最优的情况,只需当前数跟前一个数比较一下就可以了,这时一共需要比较n- 1次,时间复杂度为O(n)。   ...因为使用冒泡排序时,一趟只能选出一个最值,有n个元素最多就要执行n – 1趟比较。而使用快速排序时,一次可以将所有元素按大小分成两堆,也就是平均情况下需要logn轮就可以完成排序。   ...netherlandsFlag(arr, L, R); process2(arr, L, equalArea[0] - 1); process2(arr, equalArea[1] + 1, R); } //这个方法的目的是按...如[2,2,4,1],按间隔为2,降序排序,前两个元素的相对位置就会改变。因此,希尔排序是不稳定的排序方式。

    76650

    【数据结构】排序算法——Lessen1

    当gap > 1时都是预排序,目的是让数组更接近于有序 gap = gap / 3 + 1;后面+1是为了保证最后一次gap的值为1 当gap=1时,相当于直接插入排序,希尔排序是直接插入排序算法上改进而来的...2、选择排序 2.1直接选择排序 选择排序的基本思想是每一次从待排序的数组中选出最小(或最大)的一个数,存在起始位置,知道全部数据排完。...当某一趟并未发生交换说明此时数组已经有序,可以提前退出循环,我们可以设定一个标志来判断某一趟是否未发生交换。...,当待排集合已经接近有序时,快排的效率是很低的,如果数据量比较大还会因为函数递归太深而导致栈溢出。...,因为当左边取基准值时左边就自然而然的形成了一个“坑” 也不用分析为什么相遇位置一定比基准值小(或大)的问题,因为它相遇的位置是坑,自然而然的基准值就应该放在坑里 3.2.3 前后指针法 | 算法思路:

    10910

    多种解法破中等题

    0.说在前面1.数组中的第K个最大元素1.0 问题1.1 降序方法1.2 递归快排1.3 非递归快排1.4 最大堆排序1.5 最小堆排序2.二叉搜索树中第K小的元素2.0 问题2.1 递归中序遍历2.2...非递归中序遍历 0.说在前面 本周还差一次,今天刷两道,分别为数组中的第k个最大元素与二叉搜索树中第k小的元素!...示例 1: 输入: [3,2,1,5,6,4] 和 k = 2 输出: 5 示例 2: 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4 1.1 降序方法 【思路】 直接将数组排序即可...快排是以枢椎privot为界限,分左边与右边,我们假设是降序快排,那么枢椎左边的元素都比枢椎值本身大,右边的元素都比枢椎值本身小,这就引出了一个思想:当某次快排结束后,刚好这个枢椎放在了第k个位置上,那么我们可以确定...heappush方法实现了push数据同时调整堆!

    41510
    领券