二分查找
- 算法要求
- 二分查找过程
- 如何更新左右边界
- 实例
- type1:常规记录中间元素
- type2:取跳出循环后的左或右边界
算法要求
- 顺序存储结构
- 元素大小有序
二分查找过程
- 将元素排序;
- 将中间位置记录的这个元素与目标元素比较;
2.1 如果相同,则查找成功;
2.2 否则将元素分为前、后两部分,如果目标元素相比查找元素在左,则更新右边界;如果目标元素相比查找元素在右,则更新左边界;
2.3 重复步骤2
如何更新左右边界
- 查找区间为 [left, right],循环条件为 left <= right;左右分别更新为 mid+1、mid-1
- 查找区间为 [left, right),循环条件为 left < right;左右分别更新为 mid+1、mid
实例
type1:常规记录中间元素
- 有效的平方数
def isPerfectSquare(num):left,right=0,numwhile left<=right:mid=(left+right)//2if mid*mid==num:return Trueelif mid*mid<num:left=mid+1else:right=mid-1return False
type2:取跳出循环后的左或右边界
- 找出X的平方根
注:跳出循环时左右边界的意义,更新前的左右边界分别满足 if 后的条件
def findSqrt(x):left,right=0,xwhile left<=right:mid=(left+right)//2if mid*mid<=x:left=mid+1else:right=mid-1#跳出循环时 left>right,说明上一个更新的是 left,即(left-1)*(left-1)<=x;又 right*right>x,所以left*left>x,因此 left-1 就是要查找的目标数return left-1
- 搜索插入位置
给定一个排序数组nums和一个目标值target,返回目标值索引。如果不存在,返回它将会被按顺序插入的位置。
def searchInsert(nums, target):left,right=0,len(nums)-1while left<=right:mid=(left+right)//2if nums[mid]==target:return midelif nums[mid]<target:left=mid+1else:right=mid-1#跳出循环时后,nums[left-1]<target & nums[right]>target i.e nums[left]>target,因此target要放在left位置return left