c++二分查找边界问题
时间: 2023-10-24 15:33:44 浏览: 55
c二分查找边界问题是指在给定一个单调不减有序数组nums和一个目标值target的情况下,通过二分查找算法来确定目标值在数组中的边界位置,即左侧边界或右侧边界。
对于寻找右边界的问题,可以使用二分查找算法,在每一次比较中,如果中间值大于目标值,则将右边界更新为中间值,如果中间值小于目标值,则将左边界更新为中间值+1,如果中间值等于目标值,则将左边界更新为中间值+1。当左边界和右边界相等时,返回右边界减1的值作为右侧边界的下标。如果找不到目标值,则返回-1。
对于寻找左边界的问题,同样可以使用二分查找算法,在每一次比较中,如果中间值大于目标值,则将右边界更新为中间值,如果中间值小于目标值,则将左边界更新为中间值+1,如果中间值等于目标值,则将右边界更新为中间值。当左边界和右边界相等时,返回左边界的值作为左侧边界的下标。如果找不到目标值,则返回-1。
通过以上方法,我们可以解决c二分查找边界问题。
相关问题
二分查找右侧边界c++
右侧边界的二分查找算法可以通过以下方式表述:
```C++
int searchRightRange(vector<int>& nums, int target) {
int rightRange = -1; // 定义右侧边界的初始值为-1
int left = 0, right = nums.size() - 1; // 定义二分法的区间
while (left <= right) {
int mid = left + (right - left) / 2; // 计算要查找的位置
if (nums[mid == target) { // 查找到目标值,记录mid,然后向右继续查找
rightRange = mid;
left = mid + 1;
} else if (nums[mid < target) { // 查找的值小于目标值,改变左界向右继续查找
left = mid + 1;
} else { // 查找的值大于目标值,改变右界向左继续查找
right = mid - 1;
}
}
return rightRange; // 返回元素右侧边界的位置,若元素不存在则返回-1
}
```
这段代码采用了标准的二分查找算法,通过不断调整左界和右界的值来缩小查找范围,直到找到目标值或者查找区间为空。函数返回的是元素的右侧边界位置,如果元素不存在,则返回-1。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *2* *3* [C++:用二分法查找目标值在排序排列数组中的左右边界](https://blog.csdn.net/weixin_47356236/article/details/123015010)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 100%"]
[ .reference_list ]
c++ 二分查找及其变种
二分查找是一种高效的查找算法,适用于在已排序的数组中查找目标元素。其基本思想是将待查找范围不断二分,通过与目标元素进行比较来决定继续查找的方向,直到找到目标元素或确定不存在。
首先,设定初始的查找范围为整个数组,即左边界为0,右边界为数组长度减一。然后,计算中间位置的索引mid,获得对应的数组元素。
如果mid位置的元素等于目标元素,则找到目标,返回对应索引。
如果mid位置的元素大于目标元素,则目标元素应该在mid的左侧,更新右边界为mid-1。
如果mid位置的元素小于目标元素,则目标元素应该在mid的右侧,更新左边界为mid+1。
重复以上步骤,直到左边界大于右边界,表示整个数组已查找完毕,但未找到目标元素,返回-1。
二分查找的时间复杂度为O(log n),其中n为数组长度。
二分查找的变种有几种,例如:
1. 查找第一个匹配的元素
在循环过程中,如果mid位置的元素等于目标元素,但其前一个元素不等于目标元素,即找到第一个匹配的元素。
2. 查找最后一个匹配的元素
在循环过程中,如果mid位置的元素等于目标元素,但其后一个元素不等于目标元素,即找到最后一个匹配的元素。
3. 查找第一个大于目标元素的元素
在循环过程中,如果mid位置的元素大于目标元素,但其前一个元素小于或等于目标元素,即找到第一个大于目标元素的元素。
4. 查找最后一个小于目标元素的元素
在循环过程中,如果mid位置的元素小于目标元素,但其后一个元素大于或等于目标元素,即找到最后一个小于目标元素的元素。
这些变种通过稍微改变循环内的判断条件,可以在相同的时间复杂度下实现特定的查找需求。