快乐学算法or二分查找深度刨析

大家好，欢迎来到IT知识分享网。

目录

零、前言

一、算法思想

二、实现思路

四、源码

零、前言

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

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

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

一、算法思想

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

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

 看懂这两个例子，你现在对二分的思想应该掌握得妥妥的了。我这里稍微总结升华一下，二
分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中
间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小
为 0。

二、实现思路

1. 1. 将要查找的区间的起始位置、结束位置以及其中间位置分别记录下来。
2. 2. 拿要查找的值与区间中间位置的元素做比较，若相等则返回该位置；否则分两种情况讨论：
3.     a. 若要查找的值比中间位置元素小，则缩小查找范围至左侧区间；
4.     b. 若要查找的值比中间位置元素大，则缩小查找范围至右侧区间。
5. 3. 在新的区间中寻找中间位置，重复第二步，直到找到该元素为止。

具体步骤如下：

1. 1. 定义left=0, right=n-1表示要查找的区间的起始位置和结束位置。
2. 2. 只要left<=right,就表示区间还没有缩小到只剩一个元素，就可以继续查找，否则就表示要查找的元素不存在于数组中。
3. 3. 计算中间位置mid = (left + right) /2。
4. 4. 如果arr[mid]等于要查找的元素，返回mid；否则如果arr[mid]<要查找的元素，则将要查找的范围调整为mid+1~right，继续执行步骤3。否则将要查找的范围调整为left~mid-1，继续执行步骤3。
5. 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; }