如何通过二分法高效查找特定数据？

本文共计464个文字，预计阅读时间需要2分钟。

1. 逐个查找法：将数组中的每个数据逐个列出比较，找到目标数据即停止，最多查找i次。

2.二分查找法（折半查找法）：总体思路：将待查找的数据与区间中位数比较，逐步缩小查找范围，直至找到或确定不存在。

（1）将待查找数据与区间中位数比较。 （2）若相等，则查找成功。 （3）若待查找数据小于中位数，则在左半区间继续查找。 （4）若待查找数据大于中位数，则在右半区间继续查找。 （5）重复步骤（1）至（4），直至找到或确定不存在。

1.逐一查找法

把数组中的每一个数据逐个列出比较，若有i个数据，最多需要查找i次

2.二分法（折半查找法）

（1）大体思路：把要查找的数据反复与区间中位数比较，直至找出，若有i个数据，最多需要查找[log2i]+1次。（[]为取整符号）

（2）具体做法：假设有数列arr[]{1,2,3,4,5,6,7,8,9,10},我们要查找的元素为4。

其中mid=[（left+right）/2

(3)代码实现：

#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> int main() { int arr[] = { 2,4,6,8,10,12,14,16,18,20 }; int k = 0; scanf("%d", &k); int left = 0; int right = sizeof arr / sizeof arr[0] - 1; int mid = 0; while (left <= right) { mid = (left + right) / 2; if (k == arr[mid]) { printf("已找到，下标为%d", mid); break; } else if (k > arr[mid]) { left = mid + 1; } else right = mid - 1; } if (k != arr[mid]) printf("未找到"); return 0; }