Javascript高级—搜索算法

二分搜索

递归实现

// 递归对区间[l, r]的元素使用二分查找算法
function __binarySearch(arr, l, r, e){
	// 1. 递归终止的条件
	if (l > r) {
		return;
	}

	// 2. 开始对左右区间进行递归搜索
	var middle = Math.floor(l + (r - l) / 2);
	console.log('finding ……', middle, e, arr[middle]);
	if (e < arr[middle]) {
		// 使用递归的方法进行二分查找的时候，需要将每次递归的时候的结果返回给下一个循环调用
		return __binarySearch(arr, l, middle - 1, e);

	} else if (e > arr[middle]) {
		return __binarySearch(arr, middle + 1, r, e);
	} else {
		return middle;
	}

	// 找不到的情况的处理
	return -1;
}


function binarySearch(arr, e){
	// 实现二分查找算法(arr[0, arr.length - 1])
	return __binarySearch(arr, 0, arr.length - 1, e);
}

var arr = [1, 2, 3, 4, 5];
var res = binarySearch(arr, 5);
console.log('find ok : ', res);

非递归实现

function binary_search(arr, key) {
	var low = 0,
		high = arr.length - 1;
	while(low <= high){
		var mid = parseInt((high + low) / 2);
		if(key == arr[mid]) {
			return  mid;
		} else if(key > arr[mid]) {
			low = mid + 1;
		} else if(key < arr[mid]) {
			high = mid -1;
		} else{
			return -1;
		}
	}
};
var arr = [1,2,3,4,5,6,7,8,9,10,11,23,44,86];
var result = binary_search(arr, 10);
console.log(result); // 9