基本概念
当我们要从一个序列中查找一个元素的时候，二分查找是一种非常快速的查找算法，二分查找又叫折半查找。它对要查找的序列有两个要求，一是该序列必须是有序的（即该序列中的所有元素都是按照大小关系排好序的，升序和降序都可以，本文假设是升序排列的），二是该序列必须是顺序存储的。下图展示的就是一个能进行二分查找的序列。
算法原理
二分查找算法的原理如下：
- 如果待查序列为空，那么就返回-1，并退出算法；这表示查找不到目标元素
- 如果待查序列不为空，则将它的中间元素与要查找的目标元素进行匹配，看它们是否相等
- 如果相等，则返回该中间元素的索引，并退出算法；此时就查找成功了
- 如果不相等，就再比较这两个元素的大小
- 如果该中间元素大于目标元素，那么就将当前序列的前半部分作为新的待查序列；这是因为后半部分的所有元素都大于目标元素，它们全都被排除了
- 如果该中间元素小于目标元素，那么就将当前序列的后半部分作为新的待查序列；这是因为前半部分的所有元素都小于目标元素，它们全都被排除了
- 在新的待查序列上重新开始第1步的工作
算法模板
区间定义：[l, r) 左闭右开
其中f(m)函数代表找到了满足条件的情况，如果存在就返回对应的位置
如果没有找到,就通过g(m)函数缩小查找的范围,继续查找
def binary_search(l, r):
while l < r:
m = l + (r - l) // 2
if f(m): # 判断找了没有 (可选)
return m
if g(m): # 根据题目条件设置g(m)的策略
r = m # 新的查找范围 [l, m)
else:
l = m + 1 # 新的查找范围 [m+1, r)
return -1 # 还是没有找到 返回-1当序列中出现重复元素的时候,我们可以根据题目要求选择对应的模板进行解决
重复元素的区间:[lower_bound,upper_bound)
lower_bound(重复元素的下界): 当搜索的索引值对应的元素,大于等于目标值的时候,返回索引( nums[i] >= x )
def lowwer_bound(nums, target):
# find in range [left, right)
left, right = 0, len(nums)
while left < right:
mid = left + (right - left) // 2
if nums[mid] >= target: # g(m)
right = mid
else:
left = mid + 1
return leftupper_bound(重复元素的上界,需要将其索引减一): 当搜索的索引值对应的元素,大于目标值的时候,返回索引( nums[i] > x )
def upper_bound(nums, target):
# find in range [left, right)
left, right = 0, len(nums)
while left < right:
mid = left + (right - left) // 2
if nums[mid] > target: # g(m)
right = mid
else:
left = mid + 1
return left比如我们现在有这样一个数组:nums = [1,2,2,2,4,4,5]
lower_bound(nums,2) = 1 , upper_bound(nums,2) = 4
lower_bound(nums,3) = 4 通过判断当前索引的元素是否等于3,确定这个元素是否存在
通过上面的模板代码我们可以知道,取中间值的式子为:mid = left + (right - left) // 2
那么,为什么不是:mid = (left+right) // 2
是因为在Java等编程语言中,当(left+right)很大的时候,会出现整型数值溢出的问题,数小的时候其实没问题
在Python中其实不用考虑这个问题,Python的整型是没有限制大小的,但实际上由于机器内存的有限，我们使用的整数是不可能无限大的
所以如果你使用的Python语言做此类的算法题,取中间值的式子你用什么都可以,但是在其他编程语言中需要考虑整数数值溢出的问题
二分查找(经典例题)
题目:给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target
写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1解题思路
利用”二分查找”的思想，先找数组最中间的元素，判断其与target值的大小关系
如果该值大于target那么就选择搜索区间的左半部分继续搜索，
反之如果该值小于target那么就将搜索区间的右半部分继续搜索，
如果最终搜索区间的左右节点重合也未找到target，则表明不存在该值返回-1
class Solution:
def search(self, nums, target) -> int:
left,right = 0,len(nums)
while left < right:
mid = left + (right-left)//2
if nums[mid] == target:
return mid
if nums[mid] > target:
right = mid
else:
left = mid+1
return -1x 的平方根
实现 int sqrt(int x) 函数
计算并返回 x 的平方根，其中 x 是非负整数
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
由于返回类型是整数，小数部分将被舍去。解题思路
我们只需要在0-(x+1)的范围内找到一个数,满足m * m = x 即可满足题目要求,返回m的值即可
为什么搜索的范围是0-(x+1),取决于我们的搜索区间[l,r)
class Solution:
def mySqrt(self, x: int) -> int:
left,right = 0,x
while left<right:
mid = left+(right-left)//2
if mid**2 == x:
return mid
if mid**2 > x:
right = mid
else:
left = mid+1
return left-1为什么函数的返回值是 left-1
当出现某个整数的平方根带小数的时候,最后的结果就是left-1
比如这个数是8,那么他的平方根就是 2.82842...,传入函数中,最后的left会是3
因为在while循环中,不可能存在一个整数的平方等于8
当3(left)<3(right)的时候,也就是停止while循环的时候
此时解肯定不是left，而left是mid+1更新而来,上一个mid恰好满足mid*mid<x
所以,left-1的结果就是sqrt(8)的结果
爱吃香蕉的珂珂
珂珂喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。
警卫已经离开了，将在 H 小时后回来。
珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。
每个小时，她将会选择一堆香蕉，从中吃掉 K 根。
如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，
然后这一小时内不会再吃更多的香蕉。
珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。
示例 1：
输入: piles = [3,6,7,11], H = 8
输出: 4
示例 2：
输入: piles = [30,11,23,4,20], H = 5
输出: 30解题思路
连续的空间线性搜索，这就是二分查找可以发挥作用的标志
“如果香蕉小于K根，她将吃掉这堆的所有，并一小时内不会再吃更多香蕉”
所以我们最大值选择这个列表的max值即可
在这道题目中,我们还需要写一个函数,通过传入速度K,返回吃掉所有香蕉的用时t
再与题目给出的的H进行对比,最后返回答案即可
class Solution:
def minEatingSpeed(self, piles, h) -> int:
def cost(k):
t = 0
for pile in piles:
t += int(pile / k)
if pile % k != 0:
t += 1
return t
left,right = 1,max(piles)
while left<right:
mid = left+(right-left)//2
if cost(mid) <= h:
right = mid
else:
left = mid+1
return left
