本篇内容介绍了“C++怎么实现二分法”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！二分法是在一个排好序的序列（数组，链表等）中，不断收缩区间来进行目标值查找的一种算法，下面我们就来探究二分法使用的一些细节，以及常用的场景：寻找一个数；寻找左侧边界；寻找右侧边界。首先，我们先来分析一下右边界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] 时，需要将区间向右收缩，即第二种情况的分析类似，这里只给出结论：当left = mid+1，因为在 "左闭右开" 的区间下，新的查找区间变成 香港云主机([mid+1, right)) 才不会漏掉值。当目标值不在序列中时，需要将while的条件写成while(left 而不是写成while(left，这样会引起数组越界。nums[mid] > target时，需要将区间向左收缩，即right=mid-1；当nums[mid] 时，需要将区间向右收缩，即当目标值不在序列中时，需要将left = mid+1；while的条件写成while(left在序列中查找一个数，如果存在则返回数的索引，如果不存在则返回-1。为了方便分析，我们就只用第一种情况进行说明：上述代码只能从序列中查找一个目标值并返回位置，当一个序列中目标值不止一个时，我们需要找到目标值最左边的位置和最右边的位置，这时候二分法需要进行改写：根据上述代码，可以发现如果查找目标值的左边界，在满足nums[mid] == target时，需要缩小搜索区间的上界right，在区间 ([left, mid]) 中继续搜索，直到搜索完毕left==right。此时left=right=左边界。查找右边界的做法与左边界类似：注意这里的判断条件改成了当nums[mid] == target时，left = mid+1。因为搜索的区间为 “左闭右开”，所以在寻找左边界时可令right=mid，在寻找右边界时必须另left=mid+1，不然程序会一直停在循环里面而无法跳出循环。“C++怎么实现二分法”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注开发云网站，小编将为大家输出更多高质量的实用文章！
这篇文章主要介绍了如何解决win10系统无法打开事件查看器的问题，具有一定借鉴价值，感兴趣的朋友可以参考下，希望大家阅读完这篇文章之后大有收获，下面让小编带着大家一起了解一下。方法/步骤：1. 在键盘上按下“win”徽标键和“R”按键调出运行窗口，在运行窗口中…
免责声明：本站发布的图片视频文字，以转载和分享为主，文章观点不代表本站立场，本站不承担相关法律责任；如果涉及侵权请联系邮箱：360163164@qq.com举报，并提供相关证据，经查实将立刻删除涉嫌侵权内容。
微信扫一扫 
