当前位置：首页 > article >正文

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

article 2025/2/26 0:30:28

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]`左闭右闭情况

// 二分查找
// 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 
}