BinarySearch及其对应的经典题

BinarySearch（二分搜索）是七大搜索算法之一，又称为二分查找。它的名字很好地反映了它的基本思想。BinarySearch主要是为了将数据有序存储的集合。假设有一个集合和一个要查找的目标值，每次将目标值与集合中间的元素进行比较，将要查找的范围缩小到前一个范围的一半，例如目标值小于二分查找区间的中间值，则下一次查找区间为原区间的左半部分。重复这个过程，直到找到目标值或者区间缩小到0。下面的动画就是二分查找的基本过程，也是最简单的一类二分查找。一开始我们总是维护两个指针，分别指向数组的起始位置和结束位置。这是为了方便找到数组的中间位置。然后，在接下来的二分查找中，根据比较结果，选择移动左指针或右指针。为了减少数组的长度，二分查找的一个基本框架如下：defBinarySearch(nums,target):left,right=0,len(nums)-1whileleft<=right:mid=left+(right-left)//2#计算数组的中间位置ifnums[mid]==target:returnmid#查找并返回#中间元素大于目标值，搜索数组左半部分elifnums[mid]>target:right=mid-1#中间元素小于目标值，搜索数组右半部分elifnums[mid]nums[mid]:#右半部分是有序的ifnums[mid]target:right=mid-1elifnums[mid]=len(nums)ornums[left]!=target):return-1returnleftdefrightbount(nums,target):#找到右边界left,right=0,len(nums)-1whileleft<=right:mid=left+(right-left)//2ifnums[mid]>target:right=mid-1elifnums[mid]target:right=mid-1else:left=mid+1returnFalse二分查找比较难的部分是边际问题。比如循环条件的表达方式有很多种，有带等号的，也有不带等号的，我比较习惯用$left<=right$，等号是不是跟右指针有关，如果你是对这里的细节感兴趣的可以自行查看。他们会互相混淆，而且很容易出现越界的问题，所以找一个你认为容易理解的形式，不要随意更改。关注公众号【奶糖猫】获取更多精彩文章