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

2025 - 02 - 13 - 第 49 篇 作者(Author): 郑龙浩 / 仟濹(CSND)

二分搜索法 / 二分查找

学习课程：

.bilibili /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]左闭右闭情况 // 二分查找 // 2025-02-09 // 郑龙浩 / 仟濹 #include <iostream> #include <algorithm> using namespace std; // 左闭右闭时 int binary_search( int arr[], int size, int target ){ int middle; // 中间的数 int left = 0, right = size - 1; // 左边界 右边界 middle = size / 2; // 每次循环都找到中间的位置加以判断 // 当数组是左闭右闭的时候，则 不能写 left <= right ---> 与左闭右开相反的 // 举一个反粒子，[1, 1) 的时候，是不存在这么一个整数(既是 1， 又不是 1)的 while( left < right ){ middle = ( left + right ) / 2; // 当 arr[ middle ] > target 的時候，证明 middle 指向的位置在 target 的右边，所以right 可以向左定位到targrt - 1的位置了 // 为什么是 target 而不是 target - 1 呢？ // 因为 right 是开区间，那么 (left + right ) / 2 的时候-->实际上 right 是不在 [left, right)，但是计算的时候是按照 [left, right]计算的(不然开区间可没法算了) // 所以计算的时候 right 当作了闭区间，但实际上 middle 并不是left ~ right 的中间位置(因为right 是开区间，有点抽象，可能有点难想), 而是 【left ~ right左边一点点】 // 所以实际上 mibble 意思应该是 [left, right] / 2 往左一点点，就是 中间位置 往左一点点，所以 right 重新赋值的时候，不需要 middle - 1了， // 因为 middle 本来就是表示的【中间位置】往左一点点，也就是 left ~ middle 是不包含【中间位置】的 if( arr[ middle ] > target ) right = middle; // 但是 left 重新赋值的时候是和 闭区间一样的 else if( arr[ middle ] < target ) left = middle + 1; else return middle; } return -1; // 如果没有找到，则返回 -1 } int main( void ){ int arr[ 10 ] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int size = 10; // 数组长度 int target; // 要查找的数字 cin >> target; cout << binary_search( arr, size, target ); return 0; } 2 [left, right)左闭右开情况 // 左闭右开时 int binary_search_2( int arr[], int size, int target ){ int middle; // 中间的数 int left = 0, right = size - 1; // 左边界 右边界 middle = size / 2; // 每次循环都找到中间的位置加以判断 // 当数组是左闭右闭的时候，则 不能写 left < right // 举一个反粒子，[1, 1] 的时候，left < right 就不会进行查找了，实际上哪怕长度为 1 ，也应该进行查找 while( left <= right ){ middle = ( left + right ) / 2; // 当 arr[ middle ] > target 的時候，证明 middle 指向的位置在 target 的右边，所以right 可以向左定位到targrt - 1的位置了 // 为什么是 target - 1 而不是 target 呢？ // 因为target肯定不在middle的位置上，肯定在 left ~ middle - 1 --> if中判断的时候，已经判断出来arr[middle] > target， // 也就证明arr[middle]肯定不是要搜索的值，那么 left ~ middle 中的 middle这个位置肯定不是 target，然而 left ~ middle - 1中，middle - 1 指向的可能就是 target if( arr[ middle ] > target ) right = middle - 1; else if( arr[ middle ] < target ) left = middle + 1; else return middle; } return -1; // 如果没有找到，则返回 -1 }