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

原文地址：https://blog.csdn.net/m0_37981569/article/details/143783069

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！