二分查找求上界和下界
时间: 2023-10-24 22:30:52 浏览: 95
二分查找可以用来求解有序表中元素的上界和下界。求上界是指在有序表中查找第一个大于目标值的元素的位置,而求下界是指在有序表中查找第一个大于等于目标值的元素的位置。
对于求上界,可以使用以下算法:
int upper_bound(int *A, int x, int y, int v) {
int m;
while (x < y) {
m = x + (y - x) / 2;
if (A[m] > v)
y = m;
else
x = m + 1;
}
return x;
}
上述算法使用二分查找的思想,在有序表A中查找第一个大于目标值v的位置。通过不断缩小查找区间,直到找到上界位置或找不到为止。返回的结果x即为上界位置。
对于求下界,可以使用以下算法:
int lower_bound(int *A, int x, int y, int v) {
int m;
while (x < y) {
m = x + (y - x) / 2;
if (A[m] >= v)
y = m;
else
x = m + 1;
}
return x;
}
上述算法同样使用二分查找的思想,在有序表A中查找第一个大于等于目标值v的位置。通过不断缩小查找区间,直到找到下界位置或找不到为止。返回的结果x即为下界位置。
因此,二分查找可以用来求解有序表中的上界和下界。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* [简介二分查找算法与相关的Python实现示例](https://download.csdn.net/download/weixin_38692100/13774733)[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: 50%"]
- *2* *3* [二分查找求上下界的两种不同算法](https://blog.csdn.net/SeasonJoe/article/details/49975819)[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: 50%"]
[ .reference_list ]
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)