8、二分算法详解
二分算法（Binary Search Algorithm）是一种高效的搜索算法，用于在有序数组或有序列表中查找特定元素的位置。该算法通过将目标值与数组中间元素进行比较，并根据比较结果来确定目标值在左侧还是右侧，从而逐渐缩小搜索范围。
以下是二分算法的详细步骤：
- 确定搜索范围：初始化左边界
left 为数组的起始位置，右边界 right 为数组的结束位置。
- 进入循环：当
left 小于等于 right 时，执行以下步骤。
- 计算中间索引：通过计算
left + (right - left) / 2 得到中间索引 mid。
- 比较目标值：将目标值与中间索引对应的元素进行比较。
- 如果目标值等于中间元素，则找到了目标值，返回中间索引。
- 如果目标值小于中间元素，则说明目标值在左侧，更新
right = mid - 1。
- 如果目标值大于中间元素，则说明目标值在右侧，更新
left = mid + 1。
- 重复步骤 3-4，直到找到目标值或搜索范围缩小为空。
如果整个循环结束后仍然没有找到目标值，那么目标值不存在于数组中。
二分算法的关键点在于每次将搜索范围缩小一半。由于每次操作都会使搜索范围减半，因此二分算法的时间复杂度为 O(log n)，其中 n 是数组或列表的大小。这比线性搜索的时间复杂度 O(n) 更高效。
二分算法的模板：
| C++ |
|---|
| int binSearch(int L,int R)
{
int L=1,R=n,ans;
while(L<=R)
{
int mid= L + (R - L)/2;
if(check(mid)) ans=mid,L=mid+1;
else R=mid-1;
}
return ans;
}
|
二分算法的应用非常广泛，以下列举几个常见的应用案例：
- 有序数组查找：在一个有序数组中查找特定元素的位置。二分算法可以快速确定目标元素是否存在，并返回其索引位置。
- 查找旋转排序数组中的最小值：对于一个旋转排序数组（例如 [4, 5, 6, 7, 0, 1, 2]），可以使用二分算法来找到最小值。通过比较中间元素和两端元素来判断最小值所在的区间，并逐渐缩小搜索范围。
- 数字范围搜索：在一个有序数组或有序列表中，找到给定数字范围内的所有元素。通过两次二分查找，分别找到左边界和右边界，然后将这个范围内的所有元素返回。
- 旋转数组搜索：在一个旋转排序数组中查找目标值的位置。可以通过二分算法先确定哪一部分是有序的，然后根据目标值与有序部分的边界关系，缩小搜索范围。
- 在半有序数组中查找目标值：半有序数组是指一个数组在某个位置进行了旋转，但仍然保持部分有序。可以使用二分算法进行查找，先判断哪一部分是有序的，然后根据目标值与有序部分的边界关系，缩小搜索范围。
这些只是二分算法应用的一些常见案例，实际上，二分算法还可用于其他问题，如查找峰值元素、查找目标值的插入位置等。
有序数组查找：
| C++ |
|---|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37 | #include <iostream>
#include <vector>
using namespace std;
int binarySearch(const vector<int>& arr, int target) {
int left = 0;
int right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
int main() {
vector<int> arr = {1, 3, 5, 7, 9, 11};
int target = 7;
int index = binarySearch(arr, target);
if (index != -1) {
cout << "目标值 " << target << " 在索引 " << index << " 处找到。" << endl;
} else {
cout << "目标值 " << target << " 未找到。" << endl;
}
return 0;
}
|
查找旋转排序数组中的最小值：
| C++ |
|---|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 | #include <iostream>
#include <vector>
using namespace std;
int findMin(const vector<int>& nums) {
int left = 0;
int right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1;
} else {
right = mid;
}
}
return nums[left];
}
int main() {
vector<int> nums = {4, 5, 6, 7, 0, 1, 2};
int minVal = findMin(nums);
cout << "旋转排序数组中的最小值是：" << minVal << endl;
return 0;
}
|
数字范围搜索：
| C++ |
|---|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57 | #include <iostream>
#include <vector>
using namespace std;
vector<int> searchRange(const vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
vector<int> result(2, -1);
// 查找左边界
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
result[0] = mid;
right = mid - 1; // 继续向左查找
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
// 查找右边界
left = 0;
right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
result[1] = mid;
left = mid + 1; // 继续向右查找
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
int main() {
vector<int> nums = {1, 3, 5, 5, 7, 9};
int target = 5;
vector<int> range = searchRange(nums, target);
if (range[0] != -1 && range[1] != -1) {
cout << "目标值 " << target << " 在索引范围 [" << range[0] << ", " << range[1] << "] 内找到。" << endl;
} else {
cout << "目标值 " << target << " 未找到。" << endl;
}
return 0;
}
|
峰值元素查找：
| C++ |
|---|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 | #include <iostream>
#include <vector>
using namespace std;
int findPeakElement(const vector<int>& nums) {
int left = 0;
int right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[mid + 1]) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
int main() {
vector<int> nums = {1, 2, 3, 1};
int peakIndex = findPeakElement(nums);
cout << "峰值元素的索引为：" << peakIndex << endl;
return 0;
}
|
寻找峰值元素 II：
| C++ |
|---|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46 | #include <iostream>
#include <vector>
using namespace std;
vector<int> findPeakElement(const vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
int left = 0;
int right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
int maxRow = 0;
for (int i = 0; i < m; ++i) {
if (matrix[i][mid] > matrix[maxRow][mid]) {
maxRow = i;
}
}
bool isPeak = true;
if (mid > 0 && matrix[maxRow][mid] < matrix[maxRow][mid - 1]) {
isPeak = false;
right = mid - 1;
} else if (mid < n - 1 && matrix[maxRow][mid] < matrix[maxRow][mid + 1]) {
isPeak = false;
left = mid + 1;
}
if (isPeak) {
return {maxRow, mid};
}
}
return {-1, -1};
}
int main() {
vector<vector<int>> matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
vector<int> peakIndex = findPeakElement(matrix);
cout << "峰值元素的位置是：(" << peakIndex[0] << ", " << peakIndex[1] << ")" << endl;
return 0;
}
|
旋转有重复元素的排序数组搜索：
| C++ |
|---|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51 | #include <iostream>
#include <vector>
using namespace std;
bool search(const vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return true;
}
// 处理重复元素
if (nums[left] == nums[mid] && nums[right] == nums[mid]) {
++left;
--right;
} else if (nums[left] <= nums[mid]) {
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return false;
}
int main() {
vector<int> nums = {2, 5, 6, 0, 0, 1, 2};
int target = 0;
bool found = search(nums, target);
if (found) {
cout << "目标值 " << target << " 存在于数组中。" << endl;
} else {
cout << "目标值 " << target << " 不存在于数组中。" << endl;
}
return 0;
}
|
缺失的数字：
| C++ |
|---|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 | #include <iostream>
#include <vector>
using namespace std;
int missingNumber(const vector<int>& nums) {
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
// 如果中间元素的索引和值相等，则缺失的数字在右侧
if (nums[mid] == mid) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
int main() {
vector<int> nums = {0, 1, 3};
int missingNum = missingNumber(nums);
cout << "缺失的数字是：" << missingNum << endl;
return 0;
}
|
木材加工：
| C++ |
|---|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38 | #include <iostream>
#include <vector>
using namespace std;
int cutWood(const vector<int>& woods, int targetLen) {
int left = 1;
int right = *max_element(woods.begin(), woods.end());
int maxLen = 0;
while (left <= right) {
int mid = left + (right - left) / 2;
int count = 0;
for (int wood : woods) {
count += wood / mid;
}
if (count >= targetLen) {
maxLen = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return maxLen;
}
int main() {
vector<int> woods = {10, 20, 30};
int targetLen = 4;
int maxCutLen = cutWood(woods, targetLen);
cout << "最长切割长度为：" << maxCutLen << endl;
return 0;
}
|
本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用