折半查找法简单例题

折半查找法，也称为二分查找法，是一种常用的查找算法。该算法适用于有序表中的查找，其基本思想是将待查找的区间分成两个部分，逐步缩小区间，直到找到目标值为止。本文将介绍折半查找法的基本原理，并通过一个简单的例题进行分析。

一、折半查找法的基本原理

1. 算法流程

折半查找法的基本流程如下：

（1）首先确定待查找的区间范围（通常是整个有序表）；

（2）计算区间的中间位置 mid=(low+high)/2；

（3）用待查关键字与 middle 位置上的关键字进行比较；

（4）若相等，则找到待查元素，返回位置；

（5）若待查元素小于 middle 位置上的元素，则在左侧子区间继续查找，即 high=mid-1；

（6）若待查元素大于 middle 位置上的元素，则在右侧子区间继续查找，即 low=mid+1；

（7）重复第（2）步到第（6）步，直到找到待查元素或区间缩小为空为止。

2. 算法时间复杂度

折半查找法的时间复杂度为O(logn)，其中n为有序表中元素的个数。这是由于每次查找都将待查区间缩小为原来的一半，最多只需要 log2n 次查找就可以找到目标值。

二、折半查找法简单例题分析

假设有一个有序表 arr[]={3,5,7,9,11,13,15,17,19,21}，现在要查找其中的数字 13，应用折半查找法，其查找过程如下：

第一次查找：low=0，high=9，mid=4

arr[4]=11<13，因此在右侧子区间继续查找：low=5，high=9，mid=7

第二次查找：arr[7]=17>13，因此在左侧子区间继续查找：low=5，high=6，mid=5

第三次查找：arr[5]=13，找到待查元素，返回位置下标5。

从上述查找过程可以看出，使用折半查找法，最多只需要三次查找就可以找到元素13，其时间复杂度O(log2n)比直接查找的时间复杂度O(n)显然更优。