二分查找本质

二分查找本质二分查找说到二分查找对于稍微了解过经典算法的计算机学生来说简直太熟悉不过。能够将线性查找时间复杂度O(N)缩为O(logN)。但很多时候理解二分思想和能够在正确的场景正确的位置上使用二分之间还是有段距离了这里面需要有对于二分算法的本质理解。defbinary_search(nums,target):left,right0,len(nums)-1whileleftright:mid(leftright)//2ifnums[mid]target:returnmid# 找到直接返回elifnums[mid]target:leftmid1else:rightmid-1return-1二分本质二分查找为什么能够将线性查找时间复杂度O(N)缩为O(logN)普通查找遍历一个数组需要从头到尾挨个遍历判断而二分查找每次取中点元素进行判断满足与不满足条件都能砍掉一半待判断元素。“砍掉一半待判断元素”就是二分的本质。为了能砍掉一半待判断元素二分查找的应用才需要数组的“有序”属性这个“有序”属性可以是直观上的有顺序例如待遍历元素值递增、递减顺序等也可以是逻辑上的有顺序待求的目标值在遍历的过程中是有顺序的。结合实际例子来讲最简单的给定一个 n 个元素有序的升序整型数组 nums 和一个目标值 target 写一个函数搜索 nums 中的 target如果 target 存在返回下标否则返回 -1。输入:nums[-1,0,3,5,9,12],target9输出:4解释:9出现在 nums 中并且下标为4正常去挨个遍历时间复杂度为O(N)而使用二分每次先取中点位置元素进行条件校验这里是判断中点元素mid与目标值target的大小关系若等于则直接返回若比较大了由于序数组升序则mid右侧那一半元素肯定更大直接砍掉待遍历区间少一半若比较小了由于序数组升序则mid左侧那一半元素肯定更小直接砍掉待遍历区间少一半。这里的本质很好找直接观察元素值大小即可。再来一个例子给你两个正整数数组 spells 和 potions 长度分别为 n 和 m 其中 spells[i] 表示第 i 个咒语的能量强度potions[j] 表示第 j 瓶药水的能量强度。同时给你一个整数 success 。一个咒语和药水的能量强度 相乘 如果 大于等于 success 那么它们视为一对 成功 的组合。请你返回一个长度为 n 的整数数组 pairs其中 pairs[i] 是能跟第 i 个咒语成功组合的 药水 数目。输入spells[3,1,2],potions[8,5,8],success16输出[2,0,2]解释-第0个咒语3*[8,5,8][24,15,24]。总共2个成功组合。-第1个咒语1*[8,5,8][8,5,8]。总共0个成功组合。-第2个咒语2*[8,5,8][16,10,16]。总共2个成功组合。 所以返回[2,0,2]。正常思路就是挨个遍历spells元素spells[i]再挨个遍历potions元素potions[j]判断spells[i]*potions[j] success,若大于则res[i]此时时间复杂度O(N²)。但是我们可以想一想假如让spells或者potions升序为了让结果数据res更好赋值这里假设让potions升序那么只要spells[i]*potions[j]与success的大小关系判断出来了例如spells[i]*potions[j] success那么由于升序关系spells[i]*potions[j...n-1]即spells[i]*potions[j]右边的任一元素都会更大肯定同样满足条件那么直接累计答案个数无需再遍历potions的下标j - n-1即砍掉了一半的待遍历元素。我们只需要二分找到第一个potions[j]满足spells[i]*potions[j] success即可外层依旧是挨个遍历spells元素时间复杂度O(NlogN)。值得一提的是二分找到第一个目标元素数组元素不要求重复和二分查找目标元素的写法有一点区别这里还是以左闭右毕为例# 找第一个大于等于 target 的下标deflower_bound(nums,target):left0rightlen(nums)-1reslen(nums)# 兜底全部元素都小于target返回数组长度whileleftright:mid(leftright)//2ifnums[mid]target:# 当前mid符合条件先记下来去左边找更小下标resmid rightmid-1else:# 当前太小左边全部作废往右找leftmid1returnres当然以上只是两个最简单的题目例子大多数时候实际的算法题目不会将要二分的“对象”暴露的这么明显例如最大化最小值、最小化最大值等但是本质一定还是通过一个代表元素的条件判断代替一半区间元素条件判断砍掉一半待遍历元素。