二分法查找(思路和实现),二分法查找是什么?

KLQ 2020-05-13 09:24:45 java常见问答 5634

下面要给大家分享的是和算法二分法查找的相关内容,那么二分法查找思路是怎样的呢?代码应该如何实现呢?下面就让我们一起来了解一下吧!

一、二分法查找思路

首先让我们一起来看看二分法查找的思路

1、最开始,我们从数组的中间元素开始进行搜索,假如,这个元素正好是目标元素,那么搜索过程结束,否则的话,就执行下面一步。

2、假如,目标元素大于或者是小于中间元素,那么在数组大于或者是小于中间元素的那一半的区域进行查找,之后,就重复第一个步骤的操作。

3、假如,某一步的数组为空,那么这就表示找不到目标元素。

二分法查找的时间复杂度O(logn)

二、代码实现

(1)递归算法

function binarySearch(arr,low,high,key){
	if(low>high){return -1;}
	var mid=Math.floor((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);
	}
}

结果测试

二分法查找

(2)非递归算法

unction binarySearch(arr,key){
	var low=0; //数组最小索引值
	var high=arr.length-1; //数组最大索引值
	while(low<=high){
		var mid=Math.floor((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的情况,这种情况下key的值大于arr中最大的元素值或者key的值小于arr中最小的元素值
}

结果测试

二分法查找

三、延伸阅读

1、什么是二分法查找?

下面就简单的给大家来介绍一下二分法查找。

所谓的二分法查找也被叫做是折半法。

二分法查找是一种在在有序数组当中查找特定元素的搜索算法。

以上就是和二分法查找相关的内容了你都了解了吗?

想了解更多的实例内容,请继续关注奇Q工具网的java实例栏目了解吧!

推荐阅读:

数组中查找和正好是S的两个数,代码实现和思路

找出二叉树的下一个节点(代码实现和思路)

二维数组查找元素判断数组中是否含有某个元素