零、前言
今天我学习了二分查找（折半查找法），它是用于在有序集合中查找某一元素的便捷算法；算法思想易于理解，很多同学看了就觉得自己会了，但是约易于理解的东西越难掌握好，灵活运用更是难上加难。
我先举一个例子，如果我需要在1000万的数据中找出特定的某一个数，并且要求是O(n)的时间复杂度，这个时候你会怎么做呢？习惯暴力解法的同学，是不是只会依次遍历了？那这个时候肯定就超时啦！
算法的魅力在于解决生活当中的问题，而一个好的算法却能使大家受益其中。
一、算法思想
二分查找是一种非常简单易懂的快速查找算法，生活中到处可见。比如说，我们现在来做一
个猜字游戏。我随机写一个 0 到 99 之间的数字，然后你来猜我写的是什么。猜的过程中，
你每猜一次，我就会告诉你猜的大了还是小了，直到猜中为止。你来想想，如何快速猜中我
写的数字呢？
假设我写的数字是 23，你可以按照下面的步骤来试一试。（如果猜测范围的数字有偶数
个，中间数有两个，就选择较小的那个。）
7 次就猜出来了，是不是很快？这个例子用的就是二分思想，按照这个思想，即便我让你猜
的是 0 到 999 的数字，最多也只要 10 次就能猜中。
回到我们实际的开发环境，如果我们要从1000条数据中找到等于20元的订单；且已经排序完毕了，最简便的方法就是依次遍历，找不到就返回NULL；但这样太慢了，最差的情况是遍历完这1000条数据后才能找到我们需要的数据。
那到这里我们是否可以用二分的思想解决呢？
还是利用二分思想，每次都与区间的中间数据比对大小，缩小查找区间的范围。为了更加直
观，我画了一张查找过程的图。其中，low 和 high 表示待查找区间的下标，mid 表示待查
找区间的中间元素下标。
看懂这两个例子，你现在对二分的思想应该掌握得妥妥的了。我这里稍微总结升华一下，二
分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中
间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小
为 0。
二、实现思路
- 1. 将要查找的区间的起始位置、结束位置以及其中间位置分别记录下来。
- 2. 拿要查找的值与区间中间位置的元素做比较，若相等则返回该位置；否则分两种情况讨论：
- a. 若要查找的值比中间位置元素小，则缩小查找范围至左侧区间；
- b. 若要查找的值比中间位置元素大，则缩小查找范围至右侧区间。
- 3. 在新的区间中寻找中间位置，重复第二步，直到找到该元素为止。
具体步骤如下：
- 1. 定义left=0, right=n-1表示要查找的区间的起始位置和结束位置。
- 2. 只要left<=right,就表示区间还没有缩小到只剩一个元素，就可以继续查找，否则就表示要查找的元素不存在于数组中。
- 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; }
