本篇内容介绍了“C++怎么实现二分法”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！
公司主营业务：成都网站制作、成都网站建设、移动网站开发等业务。帮助企业客户真正实现互联网宣传，提高企业的竞争能力。成都创新互联公司是一支青春激扬、勤奋敬业、活力青春激扬、勤奋敬业、活力澎湃、和谐高效的团队。公司秉承以“开放、自由、严谨、自律”为核心的企业文化，感谢他们对我们的高要求，感谢他们从不同领域给我们带来的挑战，让我们激情的团队有机会用头脑与智慧不断的给客户带来惊喜。成都创新互联公司推出碾子山免费做网站回馈大家。
二分法是在一个排好序的序列（数组，链表等）中，不断收缩区间来进行目标值查找的一种算法，下面我们就来探究二分法使用的一些细节，以及常用的场景：
寻找一个数；寻找左侧边界；寻找右侧边界。
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 的初始值：
当 right=nums.size() 时，初始化的区间就变成了 ([0, right-1])，即 ([0,right))；
当right=nums.size()-1 时，初始化的区间就变成了 ([0, right])。
在第一种情况下，当 nums[mid] > target 时，需要将区间向左收缩，即 right=mid。这个做法的逻辑是：既然 mid 位置处大于 target，而查找区间又是 “左闭右开”，因此当 right=mid 时，新的查找区间变成了 ([0, mid))，这样才不会漏掉值。同理，当 nums[mid] < target 时，需要将区间向右收缩，即 left = mid+1，因为在 "左闭右开" 的区间下，新的查找区间变成 ([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==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，不然程序会一直停在循环里面而无法跳出循环。
“C++怎么实现二分法”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注创新互联网站，小编将为大家输出更多高质量的实用文章！
