二分查找本质

二分查找本质

二分查找

说到二分查找，对于稍微了解过经典算法的计算机学生来说，简直太熟悉不过。能够将线性查找时间复杂度O(N)缩为O(logN)。但很多时候，理解二分思想，和能够在正确的场景正确的位置上使用二分之间还是有段距离了，这里面需要有对于二分算法的本质理解。

defbinary_search(nums,target):left,right=0,len(nums)-1whileleft<=right:mid=(left+right)//2ifnums[mid]==target:returnmid# 找到直接返回elifnums[mid]<target:left=mid+1else:right=mid-1return-1

二分本质

二分查找为什么能够将线性查找时间复杂度O(N)缩为O(logN)？普通查找遍历一个数组，需要从头到尾挨个遍历判断，而二分查找，每次取中点元素进行判断，满足与不满足条件，都能砍掉一半待判断元素。
“砍掉一半待判断元素”就是二分的本质。为了能砍掉一半待判断元素，二分查找的应用才需要数组的“有序”属性，这个“有序”属性，可以是直观上的有顺序，例如待遍历元素值递增、递减顺序等，也可以是逻辑上的有顺序，待求的目标值，在遍历的过程中是有顺序的。
结合实际例子来讲，最简单的，给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果 target 存在返回下标，否则返回 -1。

输入:nums=[-1,0,3,5,9,12],target=9输出: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],success=16输出：[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):left=0right=len(nums)-1res=len(nums)# 兜底：全部元素都小于target，返回数组长度whileleft<=right:mid=(left+right)//2ifnums[mid]>=target:# 当前mid符合条件，先记下来，去左边找更小下标res=mid right=mid-1else:# 当前太小，左边全部作废，往右找left=mid+1returnres

当然，以上只是两个最简单的题目例子，大多数时候，实际的算法题目不会将要二分的“对象”暴露的这么明显（例如最大化最小值、最小化最大值等），但是本质一定还是：通过一个代表元素的条件判断，代替一半区间元素条件判断，砍掉一半待遍历元素。