hello-algo/codes/cpp/chapter_searching/binary_search_edge.cpp
Yudong Jin a005c6ebd3
Some improvements (#1073)
* Update avatar's link in the landing page

* Bug fixes

* Move assets folder from overrides to docs

* Reduce figures' corner radius

* Update copyright

* Update header image

* Krahets -> krahets

* Update the landing page
2024-02-07 22:21:18 +08:00

66 lines
2 KiB
C++
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

/**
* File: binary_search_edge.cpp
* Created Time: 2023-08-04
* Author: krahets (krahets@163.com)
*/
#include "../utils/common.hpp"
/* 二分查找插入点(存在重复元素) */
int binarySearchInsertion(const vector<int> &nums, int target) {
int i = 0, j = nums.size() - 1; // 初始化双闭区间 [0, n-1]
while (i <= j) {
int m = i + (j - i) / 2; // 计算中点索引 m
if (nums[m] < target) {
i = m + 1; // target 在区间 [m+1, j] 中
} else {
j = m - 1; // 首个小于 target 的元素在区间 [i, m-1] 中
}
}
// 返回插入点 i
return i;
}
/* 二分查找最左一个 target */
int binarySearchLeftEdge(vector<int> &nums, int target) {
// 等价于查找 target 的插入点
int i = binarySearchInsertion(nums, target);
// 未找到 target ,返回 -1
if (i == nums.size() || nums[i] != target) {
return -1;
}
// 找到 target ,返回索引 i
return i;
}
/* 二分查找最右一个 target */
int binarySearchRightEdge(vector<int> &nums, int target) {
// 转化为查找最左一个 target + 1
int i = binarySearchInsertion(nums, target + 1);
// j 指向最右一个 target i 指向首个大于 target 的元素
int j = i - 1;
// 未找到 target ,返回 -1
if (j == -1 || nums[j] != target) {
return -1;
}
// 找到 target ,返回索引 j
return j;
}
/* Driver Code */
int main() {
// 包含重复元素的数组
vector<int> nums = {1, 3, 6, 6, 6, 6, 6, 10, 12, 15};
cout << "\n数组 nums = ";
printVector(nums);
// 二分查找左边界和右边界
for (int target : {6, 7}) {
int index = binarySearchLeftEdge(nums, target);
cout << "最左一个元素 " << target << " 的索引为 " << index << endl;
index = binarySearchRightEdge(nums, target);
cout << "最右一个元素 " << target << " 的索引为 " << index << endl;
}
return 0;
}