网络工程师资料_东莞网站搭建哪家强_黑帽seo排名技术_企业管理培训课程视频

二分搜索

递归实现

// 递归对区间[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