利用数组进行数据查找---折半查找法（二分法）

article/2025/8/23 23:47:31

二分法查找：

1.适用情况：在一批有序数据中查找某数。
2.基本思想：选定这批数据中居中间位置的一个数与查找数比较，看是否为所找之数，若不是，利用数据的有序性，可以决定所找的数是在选定数之前还是之后，从而很快可以将查找范围缩小一半，就是一半一半的缩小范围，进而较快地找到目的数。

理论思想看似懵懵地，其实我已经很简结易懂的表达了，接着就拿例题来理解如何实现二分法查找。

例题：假设数组a中的数据是按由小到大的顺序排序：-12,0，6,16,23,56,80,100,110,115；从键盘上输入一个数，判断该数是否在数组中，若在，输出所在序号。
【分析】a、首先假设low,mid和high三个变量，分别只是数组中的起始元素、中间元素与最后一个元素的过程。本题如下图：（假设要查找的数为80）
在这里插入图片描述
因为mid=23，而不是所要的80.所以还要继续进行查找。
b、接着要把范围缩小，如图所示：

c、因为b步骤中，80比mid=100小，所以新的查找区间在【56,80】，如图所示：

d、因为80大于mid=56，所以新的查找区间在【80】，如图所示：
在这里插入图片描述
此时，mid亦指向80，查找到此结束。

【C语言代码】

#include <stdio.h>
#define M 10void main(){int a[M] = {-12,0,6,16,23,56,80,100,110,115};int n,flag,low,mig,high;flag = 0;low = 0;high = M-1;printf("Please input a number :\n");scanf("%d",&n);***while(low <= high){mid = (low + high )/2;if(n == mid){flag = 1;break;}else if(n > a[mid]){low = mid + 1;}else high = mid - 1;}***if(flag == 1){printf("The index of %d is %d",n,mid);}else printf("There is not %d",n);}

上方代码的缺点在于如果从键盘输入非法的（a,b,@等），则程序在运行时需把代码运行完输出结果，显知，这样运行的效率很低。因此，要从各方面考虑代码的效率，则将代码做进一步改正。

#include <stdio.h>
#define M 10void main(){int a[M] = {-12,0,6,16,23,56,80,100,110,115};int n,flag,low,mig,high;flag = 0;low = 0;high = M-1;printf("Please input a number :\n");scanf("%d",&n);#if (0)			//宏定义：注释无用的代码块do{scanf("%d",&n);getchar();}while(n < a[0] || n > a[M-1]);#endifwhile( scanf("%d",&n) != 1){   //由于**scanf函数 是有返回值**的printf("Illegal input !!\n\Please input again!!\n");getchar();				  /*目的：把缓冲区的scanf函数的输入流消耗完，否则就无法再次重新输入。*/}***while(low <= high){mid = (low + high )/2;if(n == mid){flag = 1;break;}else if(n > a[mid]){low = mid + 1;}else high = mid - 1;}***if(flag == 1){printf("The index of %d is %d",n,mid);}else printf("There is not %d",n);}

【Java语言代码】

//演示如何利用二分查找算法定位数组元素
public class BinaryChop {public static void main(String[] args) {int item = 0; // 随机数变量int[] numbers = new int[20]; // 随机数构成的数组// 以下生成一个包含随机整数的数组loop: for (int i = 0; i < numbers.length; i++) {item = new Random().nextInt(100); // 生成一个小于100的随机整数for (int j = 0; j < i; j++) { // 遍历数组进行检查，避免塞入重复数字if (numbers[j] == item) { // 已经存在该随机数，则继续第一层循环，重新生成随机数i--; // 本次循环做了无用功，取消当前的计数continue loop; // 直接继续上一级循环}}numbers[i] = item; // 往数组填入新生成的随机数}Arrays.sort(numbers); // 对整数数组排序（默认升序排列）for (int seq=0; seq<numbers.length; seq++) { // 打印数组中的所有数字System.out.println("序号="+seq+", 数字="+numbers[seq]);}System.out.println("最后生成的随机数="+item);// 下面通过二分查找法确定目标数字排在第几位int aim_item = item; // 最后生成的整数System.out.println("准备查找的目标数字="+aim_item);int start = 0; // 二分查找的开始位置int end = numbers.length - 1; // 二分查找的结束位置int middle = 0; // 开始位置与结束位置之间的中间位置for (int count = 1, position = -1; start <= end; count++) {middle = (start + end) / 2; // 折半获得中间的位置System.out.println("折半查找的中间数字="+numbers[middle]);if (numbers[middle] > aim_item) {// 该位置的数字比目标数字大，表示目标数字在该位置左边end = middle - 1;} else if (numbers[middle] < aim_item) {// 该位置的数字比目标数字大，表示目标数字在该位置右边start = middle + 1;} else { // 找到目标数字，跳出循环position = middle;System.out.println("查找次数="+count+", 序号位置="+position);break;}}}
}