javascript实现二分法

js 实现数组查找二分法

二分法实现原理：二分查找可以解决已经排好序数组的查找问题：只要数组中包含target（即要查找的值），那么通过不断缩小包含target数组的范围，最终就可以找到它。

其算法流程如下：

开始，范围覆盖整个数组。

将数组的中间项与target进行比较，如果target比数组的中间项要小，则到数组的前半部分继续查找，反之，则到数组的后半部分继续查找。

如此，每次查找可以排除一半元素，范围缩小一半。就这样反复比较，反复缩小范围，最终就会在数组中找到target，或者确定原以为target所在的范围实际为空。

对于包含N个元素的表，整个查找过程大约要经过log(2)N次比较。

递归实现

例1：用递归二分法实现array.indexOf 功能（数组为正序排列）

function indexOf(arr,target,start,end){

	 start = start || 0;

	 end = end || arr.length - 1;

	 if(start > end){

	 	return -1;

	 }

	let mid = Math.floor((start + end)/2);

		if(arr[mid] > target) {

			end = mid-1;

			return indexOf(arr,target,start,end);

		}

		else if(arr[mid] < target){

			start = mid + 1;

			return indexOf(arr,target,start,end);

		}

		else {

			return mid;

		}

}

let a = [0,1,2,3,4,5,6,434,435];

console.log(indexOf(a,12));     //打印结果为-1

while循环实现

function indexOf(arr,target,start,end){

	 start = start || 0;

	 end = end || arr.length - 1;

	 let mid = Math.floor((start + end)/2);

	 console.log(start,end);

	 while(start <= end){

	 	console.log(start,end,target,arr[mid]);

	 	if(target > arr[mid]){

	 		start = mid + 1;

	 		mid = Math.floor((start + end)/2);

	 	}

	 	else if(target < arr[mid]){

	 		end = mid - 1;

	 		mid = Math.floor((start + end)/2);

	 	}

	 	else {

	 		return mid ;

	 	}

	 }

	 console.log(start,end);

	 return -1;

}

let a = [0,1,2,3,4,5,6,434,435];

console.log(indexOf(a,5));     //打印结果为5

巴特西

javascript实现二分法

js 实现数组查找二分法

递归实现

while循环实现

最新文章

热门文章