零、前言

今天我学习了二分查找（折半查找法），它是用于在有序集合中查找某一元素的便捷算法；算法思想易于理解，很多同学看了就觉得自己会了，但是约易于理解的东西越难掌握好，灵活运用更是难上加难。

我先举一个例子，如果我需要在1000万的数据中找出特定的某一个数，并且要求是O(n)的时间复杂度，这个时候你会怎么做呢？习惯暴力解法的同学，是不是只会依次遍历了？那这个时候肯定就超时啦！

算法的魅力在于解决生活当中的问题，而一个好的算法却能使大家受益其中。

一、算法思想

二分查找是一种非常简单易懂的快速查找算法，生活中到处可见。比如说，我们现在来做一

个猜字游戏。我随机写一个 0 到 99 之间的数字，然后你来猜我写的是什么。猜的过程中，

你每猜一次，我就会告诉你猜的大了还是小了，直到猜中为止。你来想想，如何快速猜中我

写的数字呢？

假设我写的数字是 23，你可以按照下面的步骤来试一试。（如果猜测范围的数字有偶数

个，中间数有两个，就选择较小的那个。）

7 次就猜出来了，是不是很快？这个例子用的就是二分思想，按照这个思想，即便我让你猜

的是 0 到 999 的数字，最多也只要 10 次就能猜中。

回到我们实际的开发环境，如果我们要从1000条数据中找到等于20元的订单；且已经排序完毕了，最简便的方法就是依次遍历，找不到就返回NULL；但这样太慢了，最差的情况是遍历完这1000条数据后才能找到我们需要的数据。

那到这里我们是否可以用二分的思想解决呢？

还是利用二分思想，每次都与区间的中间数据比对大小，缩小查找区间的范围。为了更加直

观，我画了一张查找过程的图。其中，low 和 high 表示待查找区间的下标，mid 表示待查

找区间的中间元素下标。

看懂这两个例子，你现在对二分的思想应该掌握得妥妥的了。我这里稍微总结升华一下，二

分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中

间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小

为 0。

二、实现思路

1. 1. 将要查找的区间的起始位置、结束位置以及其中间位置分别记录下来。
2. 2. 拿要查找的值与区间中间位置的元素做比较，若相等则返回该位置；否则分两种情况讨论：
3.    a. 若要查找的值比中间位置元素小，则缩小查找范围至左侧区间；

1.    b. 若要查找的值比中间位置元素大，则缩小查找范围至右侧区间。
2. 3. 在新的区间中寻找中间位置，重复第二步，直到找到该元素为止。

具体步骤如下：

1. 1. 定义left=0, right=n-1表示要查找的区间的起始位置和结束位置。
2. 2. 只要left<=right,就表示区间还没有缩小到只剩一个元素，就可以继续查找，否则就表示要查找的元素不存在于数组中。
3. 3. 计算中间位置mid = (left + right) /2。

4. 如果arr[mid]等于要查找的元素，返回mid；否则如果arr[mid]<要查找的元素，则将要查找的范围调整为mid+1~right，继续执行步骤3。否则将要查找的范围调整为left~mid-1，继续执行步骤3。

5. 重复上述过程，直到找到要查找的元素或确定要查找的元素不存在于数组中。

6.二分查找时间复杂度为O(log n)，是一种高效的查找算法。但需要注意的是，该算法只能针对已排序的数组进行查找，因此如果数组未排序，则需要先进行排序操作。

四、源码

#include <stdio.h>
int binary_search(int arr[], int low, int high, int target, int *index) {
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            *index = mid; // 将找到的目标值的下标通过指针返回
            return 1; // 返回 1 表示找到了目标值
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return 0; // 返回 0 表示没找到目标值
}
int main() {
    int arr[] = {1, 3, 5, 7, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 1;
    int index = -1; // 初始化 index 为 -1，表示没找到目标值
    if (binary_search(arr, 0, n - 1, target, &index)) { // 如果找到了目标值
        printf("%d 在数组中的下标是 %d\n", target, index);
    } else { // 没找到目标值
        printf("没有找到 %d\n", target);
    }
    return 0;
}