# 二分查找法
二分查找法(binary search algorithm),也称折半搜索算法(half-interval search algorithm)、对数搜索算法(logarithmic search algorithm),是一种在有序数组中查找某一特定元素的搜索方法。
原理:每次跟区间中间元素对比,将待查找区域缩小一半,直到找到元素或区间缩小为0。
# 算式
给出长度为n的有序数组A及目标值T。
- 令L为0,R为n - 1;
- 如果L > R,则查找失败结束;
- 令m(中间值元素)为|(L + R) / 2|;(防止算术溢出,一半采用|L + (R - L) / 2|代替)
- 如果Am < T,令L为m + 1并回到步骤二;
- 如果Am > T,令R为m - 1并回到步骤二;
- 当Am = T,查找结束,回传值m。
这个迭代步骤会持续透过两个变量追踪搜索的边界。
# 代码实现
# 循环
function binarySearch(arr, value) {
if (!Array.isArray(arr)) {
return -1;
}
const length = arr.length;
let left = 0;
let right = length - 1;
if (value < arr[left] || value > arr[right]) {
return -1;
}
while(left <= right) {
const mid = ~~((left + right) / 2);
if (arr[mid] === value) {
return mid;
}
if (arr[mid] > value) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
# 递归
function binarySearch(arr, value, left, right) {
if (!Array.isArray(arr)) {
return -1;
}
if (!arr.length) {
return -1;
}
if (left > right) {
return -1;
}
if (value < arr[left] || value > arr[right]) {
return -1;
}
const mid = ~~((left + right) / 2);
if (arr[mid] === value) {
return mid;
}
if (arr[mid] > value) {
return binarySearch(arr, value, left, mid - 1);
} else {
return binarySearch(arr, value, mid + 1, right);
}
}