【C】折半(二分)查找

   折半查找也称为二分查找，是一种在有序数组中查找某一特定元素的搜索算法。其优点是查找速度快，缺点是所要查找的数据必须在有序序列中。

1、基本思想

   假设有一个升序排列的数组arr，在该数组中查找元素key。首先找出该数组中最中间的元素，然后将最中间的元素mid与所要查找的元素key进行比较，如果相等则返回该元素的下标。如果 mid>key ,那么在mid左边的区间去查找key，如果 mid<key ，那么在mid右边的区间中去查找key。重复上述步骤，直到找到元素key为止，假如没有找到，则返回失败。

   假设有n个元素，经过第一次查找后，查找区间缩短为 n/2，经过第二次查找后，查找区间缩短为 n/4，……那么经过k次查找后，查找区间变为n/2^k(ps: n除上2的k次方)。不难发现，k其实就是循环次数，那么最终找到元素key时，n/2^k=1(ps: 这里等于1就表示找到了元素key)，因此可以得出最坏情况下该算法的时间复杂度为O(log2n)。(ps: log2n表示以2为底，n的对数，关于时间复杂度可参考浅析时间复杂度和空间复杂度)

2、算法实现

a.设置初始查找值：left = 0，right = len - 1；

b.取中间位置mid = (left & right) + ((left ^ right) >> 1)；(ps:求left与right的平均值，可参考求平均值的4种方法)

c.比较key与arr[mid]的大小，

   若 arr[mid] == key，则表示查找成功，返回该元素在数组arr中的下标mid，

   若 arr[mid] > key，则表示查找区间应该更新为mid左半区间，right = mid - 1，

   若 arr[mid] < key，则表示查找区间应该更新为mid右半区间，left = mid + 1，

d.重复上述步骤，如果还没有找到元素key，则返回失败。

3、源代码

#define _CRT_SECURE_NO_WARNINGS 1

/*
* Copyright (c) 2018, code farmer from sust
* All rights reserved.
*
* 文件名称：BinarySearch.c
* 功能：折半查找，又称为二分查找，旨在查找一个排好顺序的数组中的某个元素
*
* 当前版本：V1.0
* 作者：sustzc
* 完成日期：2018年3月28日22:07:28
*/

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

/*
*	函数名称：BinarySearch
*
*	函数功能：二分查找排好序的数组中的某个元素
*
*	入口参数：pArr, key, len
*
*	出口参数：mid
*
*	返回类型：int
*/

int BinarySearch(int * pArr, int key, int len)
{
	int left = 0;
	int right = len - 1;
	int mid = 0;

	assert(NULL != pArr);
	
	while (left <= right)
	{
		mid = (left & right) + ((left ^ right) >> 1);

		if (pArr[mid] == key)
		{
			return mid;
		}
		else if (pArr[mid] > key)
			{
				right = mid - 1;	
			}
			else
			{
				left = mid + 1;
			}
	}

	return -1;
}

int main(void)
{
	int arr[] = {1,2,3,4,5,6,7,8,9,10};
	int key = 7;
	int len = sizeof(arr) / sizeof(int);
	int ret = BinarySearch(arr, key, len);
	
	if (-1 == ret)
	{
		printf("没找到%d!\n", key);
	}
	else
	{
		printf("找到了%d，它的下标是%d\n", key, ret);
	}

	return 0;
}

4、输出结果

若将数组arr中的元素7去掉，再次运行程序。