【C语言】折半查找

wander

折半查找      

指在已经排好序的一组数据中快速查找数据。它的算法复杂度非常低，但它要求数据必须是已经排好序的。比如数组 a 中：

13  45  78  90  127  189  243  355

现在看看怎么用折半算法在其中查找 243。
1) 先定义一个变量 key 用于存放要查找的 243：

key = 243

2) 定义变量 low、mid和high 分别存储数组的最小下标、中间下标和最大下标。并有：

mid = (low+high)/2 = (0+7)/2 = 3

3) 此时 a[3]=90，而 key>90，说明 243 在 90 的右边，则往后查找：

low = mid + 1 = 4

4) 然后重新更新 mid：

mid = (4+7)/2 = 5

5) 此时 a[5]=189，而 key>189，说明 243 在 189 的右边，继续往后查找：

low = mid+1 = 6

6) 然后重新更新 mid：

mid = (6+7)/2 = 6

7) 此时 a[6]=key=243，找到了。

下面再来怎么查找 78：
1) key=78，mid=(low+high)/2=(0+7)/2=3。

2) 此时 a[3]=90，而 key<90，说明 78 在 90 的左边，则往前查找：

high = mid-1 = 2

3) 然后重新更新 mid：

mid = (0+2)/2 = 1

4) 此时 a[1]=45，而 key>45，说明 78 在 45 的右边，则往后查找：

low = 1+1 = 2

5) 然后重新更新 mid：

mid = (2+2)/2 = 2

6) 此时 a[2]=key=78，就找到了。

若所查找的在数据序列中没有呢？比如查找 123：
1) key=123，mid=(low+high)/2=(0+7)/2=3。

2) 此时 a[3]=90，而 key>90，说明 123 在 90 的左边，则往后查找：

low = mid+1 = 4

3) 然后重新更新 mid：

mid = (4+7)/2 = 5

4) 此时 a[5]=189，而 key<189，说明 123 在 189 的左边，则往前查找：

high=mid-1=4。

5) 此时 low==high，如果该数仍不是要找的数的话，说明该序列中就没有该数了。

下面将这个程序写下来：

• # include <stdio.h>
• int main(void)
• {
•     int a[] = {13, 45, 78, 90, 127, 189, 243, 355};
•     int key;  //存放要查找的数
•     int low = 0;
•     int high = sizeof(a)/sizeof(a[0]) - 1;
•     int mid;
•     int flag = 0;  //标志位, 用于判断是否存在要找的数
•     printf("请输入您想查找的数:");
•     scanf("%d", &key);
•     while ((low <= high))
•     {
•         mid = (low + high) / 2;
•         if (key < a[mid])
•         {
•             high = mid - 1;
•         }
•         else if (a[mid < key)
•         {
•             low = mid +1;
•         }
•         else
•         {
•             printf("下标 = %d\n", mid);
•             flag = 1;
•             break;
•         }
•     }
•     if (0 == flag)
•     {
•         printf("sorry, data is not found\n");
•     }
•     return 0;
• }
  

输出结果是：
请输入您想查找的数:78
下标 = 2
请输入您想查找的数:123
sorry, data is not found

折半查找在每次查找时都排除了一半数据，所以它的效率是非常高的，平均查找长度为 log2(n+1)-1。可见使用折半查找时，数据数量越多查找效率就越高。

但是，折半查找只适合数组，不适合链表。链表中也可以用折半查找，但是不仅不会提高效率，反而还会降低效率。因为数组可以通过下标直接找到 low、mid 和 high 对应的元素，而链表是通过指针连接起来的不连续的链，所以若要查找 low、mid 和 high 对应的元素，每次都要从第一个结点出发一个一个往后找。所以一般不在链表内使用折半查找。