LeetCode_Python_二分查找算法

算法要求

1. 顺序存储结构
2. 元素大小有序

二分查找过程

1. 将元素排序；
2. 将中间位置记录的这个元素与目标元素比较；
   2.1 如果相同，则查找成功；
   2.2 否则将元素分为前、后两部分，如果目标元素相比查找元素在左，则更新右边界；如果目标元素相比查找元素在右，则更新左边界；
   2.3 重复步骤2

如何更新左右边界

1. 查找区间为 [left, right]，循环条件为 left <= right；左右分别更新为 mid+1、mid-1
2. 查找区间为 [left, right)，循环条件为 left < right；左右分别更新为 mid+1、mid

实例

type1：常规记录中间元素

1. 有效的平方数

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：取跳出循环后的左或右边界

1. 找出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  

2. 搜索插入位置
   给定一个排序数组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