js实现二分查找算法
二分查找:是一种搜索某个值的索引的算法。
基本条件:有序的数组。
思路:1.将数组折半,分成左右两个数组。
2.判断要查找的数和中间位置数值的大小,来判断要查找的数实在哪一半。
3.之后继续折半查找,直至找到这个数。
方法:二分查找有两种方法,一种是非递归方式,采用while方式,判断是否符合要求。另一种是采用递归方式,采用if方式,依次递归,找到相应的值。
步骤一(非递归):
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;
}
}
}
步骤二 (递归):
/**
*
* @param {*} arr 已排好的数组
* @param {*} low 第一个值的索引
* @param