二分查找 O(logn)

文章目录

• 一、二分法原理
• 二、二分法化简应用
• 三、二分法代码实现

一、二分法原理

二分法应用于查找元素。
在有序数组中，将数组中间值与待查找元素进行比较，不断递归进而缩小范围。

eg.在1-100内猜中对方心中的数字。(假设对方心中所想数字为80）
那么聪明的猜法是：
首先猜50 --小了
再猜75 --小了
再猜87 --大了
……
直到猜到80

由此可将每次合理范围内中间值与待查找元素进行比较，并改变待查找范围的功能设为一个函数，进行递归。当查找到该元素（返回位置），或范围为1且不含待查找元素（返回-1）时退出。

二、二分法化简应用

当进行多重循环时，可考虑使用二分搜索减小时间复杂度。
例如，在给定数组里选出四个数x1、x2、x3、x4，要求其和为W，则可考虑：
（1）将x4转化为，W-x1-x2-x3，判断所需x4在数组中是否存在
（2）将x3+x4转化为W-x1-x2，判断所需x3+x4的值是否存在。
此时我们可建立数组kk存放所有x3+x4的值，进而进行二分搜索。

三、二分法代码实现

非递归法

function binarySearch(var *arr,var key)
{//key是待查找元素
	var low=0; //数组最小索引值
	var high=arr.length-1; //数组最大索引值
	while(low<=high)
	{
		var mid=(low+high)/2;
		if(key==arr[mid])
		{
			return mid;
		}
		else if(key>arr[mid])
		{
			low=mid+1;//换范围
		}
		else
		{
			high=mid-1;//换范围
		}
	}
	return -1; //low>high的情况，说明没有该值
}

递归法

function binarySearch(var *arr,var low,var high,var key)
{
	if(low>high)
	{
		return -1;
	}
	var mid=(low+high)/2;
	if(key==arr[mid])
	{
		return mid;
	}
	else if(key<arr[mid])
	{
		high=mid-1;
		return binarySearch(arr,low,high,key);
	}
	else
	{
		low=mid+1;
		return binarySearch(arr,low,high,key);
	}
}