How to realize dichotomy in C++

This article introduces the relevant knowledge of "how to realize dichotomy in C++". In the operation process of actual cases, many people will encounter such difficulties. Next, let Xiaobian lead you to learn how to deal with these situations! I hope you can read carefully and learn something!

Dichotomy is an algorithm that continuously shrinks intervals to find target values in a sorted sequence (array, linked list, etc.). Here we will explore some details of dichotomy use and common scenarios:

Find a number; find the left boundary; find the right boundary.

int binarySearch(vector& numbers, 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){ //Condition 2: The middle value is greater than the target value } else if(nums[mid]

< target){ // 条件三：中间的值小于目标值 } } return -1; } 首先，我们先来分析一下右边界 right 的初始值： 当 right=nums.size() 时，初始化的区间就变成了 ([0, right-1])，即 ([0,right))； 当right=nums.size()-1 时，初始化的区间就变成了 ([0, right])。 在第一种情况下，当 nums[mid] >

If target, the interval needs to be contracted to the left, i.e. right=mid. The logic of this approach is: since mid is greater than target, and the search interval is "left closed and right open," when right=mid, the new search interval becomes ([0, mid)), so that no value is missed. Similarly, when nums[mid]

< target 时，需要将区间向右收缩，即 left = mid+1，因为在 "左闭右开" 的区间下，新的查找区间变成 ([mid+1, right)) 才不会漏掉值。当目标值不在序列中时，需要将 while 的条件写成 while(left < right) 而不是写成 while(left target 时，需要将区间向左收缩，即 right=mid-1； 当 nums[mid] < target 时，需要将区间向右收缩，即 left = mid+1； 当目标值不在序列中时，需要将 while 的条件写成 while(left 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; //The middle value is greater than the target value, shrinking the interval to the left } 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; //The middle value is greater than the target value, shrinking the interval to the left } else if(nums[mid] < target){ left = mid+1;//middle value is less than target value, contraction interval to right } } return left-1; }

Note that the criterion here is changed to left = mid+1 when nums[mid] == target. Because the search interval is "left closed right open," so when looking for the left boundary can make right=mid, when looking for the right boundary must also be left=mid+1, otherwise the program will always stop inside the loop and can not jump out of the loop.

"C++ how to achieve dichotomy" content is introduced here, thank you for reading. If you want to know more about industry-related knowledge, you can pay attention to the website. Xiaobian will output more high-quality practical articles for everyone!