C++实现二分法详解

⼆分法是在⼀个排好序的序列（数组，链表等）中，不断收缩区间来进⾏⽬标值查找的⼀种算法，下⾯我们就来探究⼆分法使⽤的⼀些细节，以及常⽤的场景：1. 寻找⼀个数；2. 寻找左侧边界；3. 寻找右侧边界。

⼀、⼆分法的通⽤框架

int binarySearch(vector& nums, int target){ int left=0, right=nums.size(); while(left < right) {

int mid=(left+right)/2; if(nums[mid] == target){

// 条件⼀：中间的值与⽬标值相同 }

else if(nums[mid] > target){

// 条件⼆：中间的值⼤于⽬标值 }

else if(nums[mid] < target){

// 条件三：中间的值⼩于⽬标值 } }

return -1; }

⾸先，我们先来分析⼀下右边界 right 的初始值：

1. 当 right=nums.size() 时，初始化的区间就变成了 [0,right−1][0,right−1]，即 [0,right)[0,right)；2. 当right=nums.size()-1 时，初始化的区间就变成了 [0,right][0,right]。

在第⼀种情况下，当 nums[mid] > target 时，需要将区间向左收缩，即 right=mid。这个做法的逻辑是：既然 mid 位置处⼤于 target，⽽查找区间⼜是 “左闭右开”，因此当 right=mid 时，新的查找区间变成了 [0,mid)[0,mid)，这样才不会漏掉值。同理，当 nums[mid] < target 时，需要将区间向右收缩，即 left = mid+1，因为在 \"左闭右开\" 的区间下，新的查找区间变成 [mid+1,right)[mid+1,right) 才不会漏掉值。当⽬标值不在序列中时，需要将 while 的条件写成 while(left < right) ⽽不是写成 while(left<=right)，这样会引起数组越界。第⼆种情况的分析类似，这⾥只给出结论：

当 nums[mid] > target 时，需要将区间向左收缩，即 right=mid-1；当 nums[mid] < target 时，需要将区间向右收缩，即 left = mid+1；当⽬标值不在序列中时，需要将 while 的条件写成 while(left<=right)

⼆、⼆分法查找⽬标值

在序列中查找⼀个数，如果存在则返回数的索引，如果不存在则返回 -1 。为了⽅便分析，我们就只⽤第⼀种情况进⾏说明：

int binarySearch(vector& nums, int target){ int left=0, right=nums.size(); while(left < right) {

int mid=(left+right)/2; if(nums[mid] == target){

return mid; // 查询到⽬标值，直接返回⽬标值的位置 }

else if(nums[mid] > target){

right = mid; // 中间的值⼤于⽬标值，向左收缩区间 }

else if(nums[mid] < target){

left = mid+1;// 中间的值⼩于⽬标值，向右收缩区间 } }

return -1; // 当没有找到，直接返回-1}

三、⼆分法查找⽬标值的左右边界

上述代码只能从序列中查找⼀个⽬标值并返回位置，当⼀个序列中⽬标值不⽌⼀个时，我们需要找到⽬标值最左边的位置和最右边的位置，这时候⼆分法需要进⾏改写：

// 查找⽬标值的左边界

int binarySearch(vector& nums, int target){ int left=0, right=nums.size(); while(left < right)

{

int mid=(left+right)/2; if(nums[mid] == target){

right = mid; // 查询到⽬标值不进⾏返回，⽽是收缩区间继续查找 }

else if(nums[mid] > target){

right = mid; // 中间的值⼤于⽬标值，向左收缩区间 }

else if(nums[mid] < target){

left = mid+1;// 中间的值⼩于⽬标值，向右收缩区间 } }

return left; }

根据上述代码，可以发现如果查找⽬标值的左边界，在满⾜ nums[mid] == target 时，需要缩⼩搜索区间的上界 right，在区间 [left,mid][left,mid] 中继续搜索，直到搜索完毕 left==right。此时 left=right=左边界。查找右边界的做法与左边界类似：

// 查找⽬标值的左边界

int binarySearch(vector& nums, int target){ int left=0, right=nums.size(); while(left < right) {

int mid=(left+right)/2; if(nums[mid] == target){

left = mid+1; // 查询到⽬标值不进⾏返回，⽽是收缩区间继续查找 }

else if(nums[mid] > target){

right = mid; // 中间的值⼤于⽬标值，向左收缩区间 }

else if(nums[mid] < target){

left = mid+1;// 中间的值⼩于⽬标值，向右收缩区间 } }

return left-1; }

注意这⾥的判断条件改成了当 nums[mid] == target 时，left = mid+1。因为搜索的区间为 \"左闭右开\"，所以在寻找左边界时可令 right=mid ，在寻找右边界时必须另 left=mid+1，不然程序会⼀直停在循环⾥⾯⽽⽆法跳出循环。