二分搜刮法、二分查找法【C/C ++】

2025 - 02 - 13 - 第 49 篇
作者(Author): 郑龙浩 / 仟濹(CSND)
二分搜刮法 / 二分查找

学习课程：
https://www.bilibili.com/video/BV1fA4y1o715/?spm_id_from=333.337.search-card.all.click&vd_source=2683707f584c21c57616cc6ce8454e2b
一. 二分的易错点 - 界限的选择

1 while() 中是 left < right 还是 left <= right?

选择哪一个是和
左闭右开 - [left, right)
左闭右闭 - [left, right]
**左开右闭(一般不会) ** - (left, right]
是有关系的。
2

二. 根本介绍

1 命名

• target - 要查找的数字
  
• left - 左边界
  
• right - 右边界
  
• arr - 数组
  
• size - 数组长度
  
• middle - 中心值
  

2 思绪

循环中，每次除2，确定边界，直到找到，没找到，返回-1
三 代码实现 + 思绪

1 [left, right]左闭右闭情况

1. // 二分查找
2. // 2025-02-09
3. // 郑龙浩 / 仟濹
4. #include <iostream>
5. #include <algorithm>
6. using namespace std;
7. // 左闭右闭时
8. int binary_search( int arr[], int size, int target ){
9.     int middle; // 中间的数
10.     int left = 0, right = size - 1; // 左边界 右边界
11.     middle = size / 2; // 每次循环都找到中间的位置加以判断
13.     // 当数组是左闭右闭的时候，则 不能写 left <= right ---> 与左闭右开相反的
14.     // 举一个反粒子，[1, 1) 的时候，是不存在这么一个整数(既是 1， 又不是 1)的
15.     while( left < right ){
16.         middle = ( left + right ) / 2;
17.         // 当 arr[ middle ] > target 的時候，证明 middle 指向的位置在 target 的右边，所以right 可以向左定位到targrt - 1的位置了
18.         // 为什么是 target 而不是 target - 1 呢？
19.         // 因为 right 是开区间，那么 (left + right ) / 2 的时候-->实际上 right 是不在 [left, right)，但是计算的时候是按照 [left, right]计算的(不然开区间可没法算了)
20.         // 所以计算的时候 right 当作了闭区间，但实际上 middle 并不是left ~ right 的中间位置(因为right 是开区间，有点抽象，可能有点难想), 而是 【left ~ right左边一点点】
21.         // 所以实际上 mibble 意思应该是 [left, right] / 2 往左一点点，就是 中间位置 往左一点点，所以 right 重新赋值的时候，不需要 middle - 1了，
22.         // 因为 middle 本来就是表示的【中间位置】往左一点点，也就是 left ~ middle 是不包含【中间位置】的
23.         if( arr[ middle ] > target )    right = middle;
24.         // 但是 left 重新赋值的时候是和 闭区间一样的
25.         else if( arr[ middle ] < target )   left = middle + 1;
26.         else    return middle;
27.     }
28.     return -1; // 如果没有找到，则返回 -1
29. }
32. int main( void ){
33.     int arr[ 10 ] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
34.     int size = 10; // 数组长度
35.     int target; // 要查找的数字
36.     cin >> target;
37.     cout << binary_search( arr, size, target );
38.     return 0;
39. }

复制代码

2 [left, right)左闭右开情况

1. // 左闭右开时
2. int binary_search_2( int arr[], int size, int target ){
3.     int middle; // 中间的数
4.     int left = 0, right = size - 1; // 左边界 右边界
5.     middle = size / 2; // 每次循环都找到中间的位置加以判断
7.     // 当数组是左闭右闭的时候，则 不能写 left < right
8.     // 举一个反粒子，[1, 1] 的时候，left < right 就不会进行查找了，实际上哪怕长度为 1 ，也应该进行查找
9.     while( left <= right ){
10.         middle = ( left + right ) / 2;
11.         // 当 arr[ middle ] > target 的時候，证明 middle 指向的位置在 target 的右边，所以right 可以向左定位到targrt - 1的位置了
12.         // 为什么是 target - 1 而不是 target 呢？
13.         // 因为target肯定不在middle的位置上，肯定在 left ~ middle - 1 --> if中判断的时候，已经判断出来arr[middle] > target，
14.         // 也就证明arr[middle]肯定不是要搜索的值，那么 left ~ middle 中的 middle这个位置肯定不是 target，然而 left ~ middle - 1中，middle - 1 指向的可能就是 target
15.         if( arr[ middle ] > target )    right = middle - 1;
16.         else if( arr[ middle ] < target )   left = middle + 1;
17.         else    return middle;
18.     }
19.     return -1; // 如果没有找到，则返回 -1
20. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。