二分查找

　

二分查找

上篇博客中，我们以一个小例子探索了“搜索”初步，通过介绍的两种方法，可以观察到：在数组中，当搜索某一数据时，我们采用的方法往往是遍历整个数组，然后对每一个数据依次进行比对检验，观察是否是要寻找的那个数据。这是一种普遍的处理方式，但是，当数据有序排列时，这样的方式开销会不会大了点呢？所以，下面就介绍一种新的解决办法--->二分查找。

二分查找又称折半查找，具体过程如下：（假设表中元素是按升序排列）

将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
int search(int a[], int key, int len)
{
	int ret = -1;
	int left = 0;
	int right = len - 1;
	while (left <= right)//这里一定是<=,不能只是<
	{
		int mid = (left + right) / 2;
		if (key > a[mid])
		{
			left = mid + 1;
		}
		else if (key < a[mid])
		{
			right = mid - 1;
		}
		else
		{
			ret = mid;
			break;
		}
	}
	return ret;
}
int main()
{
	int a[] = { 2, 4, 7, 11, 13, 16, 21, 24, 27, 32, 36, 40, 46 };
	int sz = sizeof(a) / sizeof(a[0]);
	int key = 0;
	scanf("%d", &key);
	int ret = search(a,key , sz);
	if (ret != -1)
	{
		printf("%d在第%d个位置\n", key, ret);
	}
	else
	{
		printf("不存在\n");
	}
	system("pause");
	return 0;
}

运行结果：

注意：循环条件一定是<=,不能只是<。以上题为例，如果循环条件是left<right;则到了第（3）步，right=mid-1=10,这时left也等于10，a[10]正好是36，但是由于left已经与right相等，所以不再循环进行判断，最后的结果是“不存在”

相关阅读

[算法总结] 二分查找

本文首发于我的个人博客：尾尾部落 二分查找法作为一种常见的查找方法，将原本是线性时间提升到了对数时间范围，大大缩短了搜索时间