二分查找详解

简述

二分查找也称折半查找（Binary Search）

二分查找是一种效率较高的查找方法。

使用二分查找的条件（同时满足）

1. 折半查找要求线性表必须采用顺序存储结构

     2.表中元素按关键字有序排列（有序）

工作原理

二分查找的工作原理：将要查找的元素一分为两半然后一半一半的查找

通过不停的缩小查找范围，改变L,R M,，直到它们三在一个元素上，并且这个元素等于查找元素

每次L和R移动的步长为1

下面将以有序数组： 1 2  3 4 5 6 7 8 9 10 进行详细说明

要查找的元素为4

1. 将要进行查找的数组看成是一个范围，左界称为Left,右界称之为Right

2.确定中间值（Middle）：数组最高下标除以2，比如：7/2=3

3. 将5和4进行比较，因为是有序的，所以比4大的都在5的右边，比4小的都在5的左边

4.发现查找元素4在中间值5的左边，改变查找大范围：L,R.   改变中间值M

 5.将查找元素4与中间值2进行比较，因为是有序的，所以这次应该将范围缩小到2右边，4左边。

6.发现查找范围在查找元素4在2和4之间，改变查找范围：L,R，改变中间值M

 7.在重复进行上述比较，直到R和L和M都是一个元素。

 8.将这个元素与要查找的元素进行比较，若相等则成功查找到元素，反之，则证明查找元素不在该有序数组中

代码实现：

//返回这个结构的下标
//二分查找-返回这个结构的下标
//<<多少等于乘以2的多少次方，>>多少等于除以2的多少次方。
#include<stdio.h>
int Binary_Search(int arr[], int len, int findval)//arr[]用来接收数组，len接收数组长度，findval用来接收查找的值
{
	int left, right, mid;//左界线，右界线，中间值
	left = 0;//左界是从第一个元素开始，下标为0的
	right = len - 1;//右界限为最右边，也就是下标为len-1的元素
	while (left <= right)
	{
		//第一步：确定中位数Middle
		mid = left + ((right - left) >> 1);
		//第二步：要查找的元素和中位数比较
		if (findval == arr[mid])
		{
			return mid;//如果要查找的数和中间值相等就返回这个中间值,如果不相等就到第三步
		}
		//第三步：缩小区间
		if (arr[mid] > findval)//以升序为例，数组在前半个区间
			right = mid - 1;
		if (arr[mid] < findval)
			left = mid + 1;

	}
	return -1;//如果要查找的有序数组中，不存在查找元素，则返回一个不存在的结果，表示查找失败
}
int main()
{

}

总结

二分查找是一项效率很高的排序方法，但是却不意味着，任何情况下都可以使用二分查找。

功能越强大的东西，使用起来的门槛也就越高

在使用二分查找时一定要注意使用条件，当两个条件同时满足的时候才可以使用它。