折半查找

发表于

思路

在有序队列中，将查找的关键字和查找范围内的中间元素进行比较，会出现如下三种情况：

  1. 关键字和该中间元素相等，则查找成功。
  2. 如果关键字比该中间元素大，则将整个查找范围的后半部分作为新的查找范围，重新进行折半查找算法。
  3. 如果关键字比该中间元素小，则将整个查找范围的前半部分作为新的查找范围，重新进行折半查找算法。
  4. 中间元素不等于关键字且查找范围小于等于1，则说明查找失败。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#include <stdio.h>
#include <stdlib.h>

int binary_search(int * data, int len,int key)
{
	int low = 0;
	int high = len - 1;
	int mid = 0;
	/* 判断查找范围是否大于等于0  */
	while (low <= high)    
	{
	    /* 首先取中间值 */
		mid = low + (high - low) / 2;
		/* 相等，则直接返回 */
		if (data[mid] == key)
		{
			return mid + 1;
		}
		/* 小于则，取前半部分 */
		else if (data[mid] > key)
		{
			high = mid - 1;
		}
		/* 大于则，取后半部分 */
		else
		{
			low = mid + 1;
		}
	}
	return -1;
}

int main()
{
	int data[5] = { 10, 2, 20, 15, 16 };
	int len = 5;
	printf("%d\n", binary_search(data, len, 20));
	return 0;
}

折半查找性能分析

查找算法性能的指标就两个：

  • 查找成功时，平均的查找长度，折半查找平均查找长度为：((n+1)/n)*(log(n+1)-1)
  • 查找失败时，需要比较的次数, 折半查找最多比较次数为：log(n)+1

注意：折半查找为有序表查找算法，它不适用于无序的顺序表和链表中。