Day 10 - Pre-Knowledge for Binary Search

Day10 - 二分查找前置知识

1. 二分查找介绍

顾名思义二分查找是一种搜索算法（折半查找），常用在有序数组中查找一个目标值。 二分查找将目标值与数组的中间元素进行比较，来决定是在数组的左半边还是右半边查找目标值，然后在符合条件的半边继续进行二分查找，直到找到目标或符合条件的半边为空。使用二分查找可以在O(logn)时间内完成一个指定元素的搜索。

举个例子，给定一个有序数组arr=[1, 2, 3, 5, 8, 13, 21]，让我们找到数组中13所在的位置索引。

最简单的方法就是遍历数组，这样需要将数组中的元素跟目标值比较6次我们才能得到13所在的位置索引。

如果使用二分查找，我们首先需要定义两个索引L指向数组第一个元素，R指向数组最后一个元素，即L = 0, R = len(arr) - 1 = 6，我们在[0, 6]这个区间搜索目标值13，然后计算数组中间元素的索引Mid = (L + R) / 2 = 3，此时数组中间元素为arr[3] = 5。

因为5 < 13，所以更新L = Mid + 1 = 4，R = 6保持不变，我们继续在[4, 6]这个区间搜索目标值13。 此时搜索区间的中间元素的索引为 Mid = (L + R) / 2 = 5，因为arr[5] = 13，所以我们找到了目标值13。

整个搜索过程只将数组中元素跟目标值比较了2次，相比第一种遍历数组（线性搜索），速度提高了3倍，实际上数组中元素越多，二分查找的查找速度优势越明显。

2. 二分查找实现

有两种方式

2.1. 迭代法

#include <iostream>
using namespace std;

// 二分查找算法
int binarySearch(int arr[], int L, int R, int target)
{
    while (L <= R)
    {
        // 计算中间位置索引
        int Mid = (L + R) / 2;
        // 如果中间位置元素等于目标值，则返回索引
        if(arr[Mid] == target)
        {
            return Mid;
        }
        // 如果中间位置元素小于目标值
        else if(arr[Mid] < target)
        {
            // 更新左边界为中间位置索引+1
            L = Mid + 1;    // 确保L有机会大于R
        }
        // 如果中间位置元素大于目标值
        else if(arr[Mid] > target)
        {
            // 更新右边界为中间位置索引-1
            R = Mid - 1;    // 确保R有机会小于L
        }
    }
    // L > R，表示没有找到目标值，返回-1
    return -1;
}

int main(void)
{
    // 测试代码
    int arr[] = {1, 2, 3, 5, 8, 13, 21};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 13;
    int result = binarySearch(arr, 0, n - 1, target);
    if (result == -1)
    {
        cout << "Target is not present in array" << endl;
    }
    else
    {
        cout << "Target is present at index " << result << endl;
    }
    return 0;
}

代码输出为：

Target is present at index: 5

时间复杂度： O(logn)，其中n为数组的长度。

空间复杂度： O(1)。

2.2. 递归法

#include <iostream>
using namespace std;

// 递归法:
int binarySearchRecursive(int arr[], int L, int R, int target)
{
    // 没有找到目标值，返回-1
    if (L > R)
    {
        return -1;
    }
    int Mid = (L + R) / 2;
    // 如果中间位置元素等于目标值，结束递归，返回索引
    if (arr[Mid] == target)
    {
        return Mid;
    }
    // 如果中间位置元素小于目标值，继续递归去右边区间[Mid+1, R]
    else if (arr[Mid] < target)
    {
        return binarySearchRecursive(arr, Mid + 1, R, target);
        // 实则 Mid + 1 == L
    }
    // 如果中间位置元素大于目标值，继续递归去左边区间[L, Mid-1]
    else if (arr[Mid] > target)
    {
        return binarySearchRecursive(arr, L, Mid - 1, target);
        // 实则 Mid - 1 == R
    }
    return 0;	// 这一句其实可以不加，但是会报出非空函数无返回值的警告......
}


int main(void)
{
    // 测试代码
    int arr[] = {1, 2, 3, 5, 8, 13, 21};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 13;
    int result = binarySearchRecursive(arr, 0, n - 1, target);
    if (result == -1)
    {
        cout << "Target is not present in array" << endl;
    }
    else
    {
        cout << "Target is present at index: " << result << endl;
    }
    return 0;
}

代码输出为：

Target is present at index: 5

时间复杂度：O(logn)，其中n为数组的长度。

空间复杂度：O(logn)，因为递归是通过栈来实现的。

3. 注意的点

1. 进行二分查找前，数组中的元素必须是有序的。

2. 二分查找实际上也是用的双指针法，双指针指向的应该是数组中的元素，所以在实现二分查找的时候索引 R最好是指向数组的最后一个元素，即R = len(arr) - 1。当然也有些同学习惯把索引R指向数组越界后的一个元素，即R = len(arr)。两种方式在搜索过程中跳出搜索的条件有些差异（L <= R 和 L < R之间的差异），只要能获得正确答案都可以，不过国内外的算法教科书上还是采用了第一种R = len(arr) - 1。这里只是给大家一个提示，不至于看到其他写法一脸懵，习惯于一种方式就好了，在代码实现的时候可以在纸上模拟一个简单的例子，确保边界条件都考虑到了。

3. 要注意边界情况的处理，考虑数组中只有一个元素或两个元素需不需要特殊处理，以及索引L，R的移动条件。

4. 二分查找应用

1. 二分查找可以用作机器学习中算法构建，例如查找模型的最佳超参数。

2. 可用于计算机图形学中的搜索，例如光线追踪或纹理映射的算法。

3. 可以用来查找数据库。