【入门】二分查找右侧边界
时间: 2023-08-27 14:14:05 浏览: 152
二分查找右侧边界是指在一个有序数组中查找某个目标值的最右边位置。下面是一个简单的实现示例:
```python
def binary_search_right(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] <= target:
left = mid + 1
else:
right = mid - 1
# 此时 left 指向的就是右侧边界的下一个位置
return left - 1 if left > 0 else -1
```
在这个示例中,我们使用了经典的二分查找算法,但是将等号的判断条件稍作修改。当中间值小于等于目标值时,我们将左边界 `left` 移动到 `mid + 1` 的位置;否则,将右边界 `right` 移动到 `mid - 1` 的位置。这样,当循环结束时,`left` 指向的就是右侧边界的下一个位置。
需要注意的是,如果数组中不存在目标值,那么返回的结果是 `-1`。你可以将这个函数应用于有序数组中,以查找目标值的最右边位置。
相关问题
二分查找右侧边界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++二分查找边界问题
c二分查找边界问题是指在给定一个单调不减有序数组nums和一个目标值target的情况下,通过二分查找算法来确定目标值在数组中的边界位置,即左侧边界或右侧边界。
对于寻找右边界的问题,可以使用二分查找算法,在每一次比较中,如果中间值大于目标值,则将右边界更新为中间值,如果中间值小于目标值,则将左边界更新为中间值+1,如果中间值等于目标值,则将左边界更新为中间值+1。当左边界和右边界相等时,返回右边界减1的值作为右侧边界的下标。如果找不到目标值,则返回-1。
对于寻找左边界的问题,同样可以使用二分查找算法,在每一次比较中,如果中间值大于目标值,则将右边界更新为中间值,如果中间值小于目标值,则将左边界更新为中间值+1,如果中间值等于目标值,则将右边界更新为中间值。当左边界和右边界相等时,返回左边界的值作为左侧边界的下标。如果找不到目标值,则返回-1。
通过以上方法,我们可以解决c二分查找边界问题。