解剖前端面试之二分查找算法
二分法查找，也称为折半法，是一种在有序数组中查找特定元素的搜索算法。
二分法查找的思路如下：
（1）首先，从数组的中间元素开始搜索，如果该元素正好是目标元素，则搜索过程结束，否则执行下一步。
（2）如果目标元素大于/小于中间元素，则在数组大于/小于中间元素的那一半区域查找，然后重复步骤（1）的操作。
（3）如果某一步数组为空，则表示找不到目标元素。
二分法查找的时间复杂度O(logn)。
先看一个解法
function binarySearch(argTarget, argArry) {
let count = 0;
let startIndex = 0,
endIndex = argArry.length - 1;
while (startIndex < endIndex && count++ < 1600) {
debugger;
let middleIndex = ((startIndex + endIndex) / 2) | 0;
let number = argArry[middleIndex];
if (number === argTarget) {
return middleIndex;
} else if (number > argTarget) {
endIndex = middleIndex;
} else {
startIndex = middleIndex;
}
}
return -1;
}
特意加了count变量防止陷入死循环
用 console.log(binarySearch(0, [0, 1, 2, 3])); 输出为0，直到2的时候都会成功，
接下来请打开Chrome开发者工具，用console.log(binarySearch(3, [0, 1, 2, 3]));做测试，多点几次startIndex一直在2，endIndex一直在3。
长按如下按钮，点击第二个会输出 -1 。
middleIndex 位置上没有匹配的话，显然不用继续参与运算了，所以应改为endIndex = middleIndex - 1;、startIndex = middleIndex + 1;
这次没有陷入死循环，startIndex是3，endIndex是3，再算一次就可以找到，循环条件要改为while (startIndex <= endIndex && count++ < 1600)。
改动之后
function binarySearch(argTarget, argArry) {
let count = 0;
let startIndex = 0,
endIndex = argArry.length - 1;
while (startIndex <= endIndex && count++ < 1600) {
debugger;
let middleIndex = ((startIndex + endIndex) / 2) | 0;
let number = argArry[middleIndex];
if (number === argTarget) {
return middleIndex;
} else if (number > argTarget) {
endIndex = middleIndex - 1;
} else {
startIndex = middleIndex + 1;
}
}
return -1;
}
当startIndex比endIndex小1时，((startIndex + endIndex) / 2) | 0导致middleIndex偏向小的数， 如果目标在endIndex上会出现问题，startIndex = middleIndex + 1;弥补了这一问题，使得程序需要再算一次才能确认endIndex是否匹配，同时与 endIndex = middleIndex - 1 一样，这样做可以减少查找的次数。
写一段用于验证的代码
for (let i = 0; i <= 20; i++) {
console.group(`长度为${i}的数组开始`);
let arr = [];
for (let j = 0; j < i; j++) {
arr[j] = j;
}
arr.forEach((el) => {
console.group(`查找元素${el}开始`);
let index = binarySearch(el, arr);
console.log(`位置为${index}`);
console.assert(!(index === -1 || arr[index] !== el), "没找到");
console.groupEnd(`查找元素${el}结束`);
});
let noFound = binarySearch(-1, arr);
console.assert(noFound === -1, "未找到元素返回值不为-1");
console.groupEnd(`长度为${i}的数组结束`);
}
endIndex = middleIndex - 1;还是endIndex = middleIndex ;都能通过测试，
当查找的数偏向左侧时会起到作用，已长度为20，查找0为例
endIndex = middleIndex ;为5次
endIndex = middleIndex - 1 ;为4次
然而并非数组越长越明显，长度为200000，查找0也是少一次
while循环再编写过程中很容易卡死，看一下递归的解法:
function binarySearch(argTarget, argArry) {
function deal(startIndex, endIndex) {
let middleIndex = ((startIndex + endIndex) / 2) | 0;
let number = argArry[middleIndex];
if (number === argTarget) {
return middleIndex;
} else if (number > argTarget) {
endIndex = middleIndex - 1;
} else {
startIndex = middleIndex + 1;
}
if (startIndex <= endIndex) {
return deal(startIndex, endIndex);
}
}
let index = deal(0, argArry.length - 1);
return index === undefined ? -1 : index;
}
考虑倒序的情况:
测试函数在查找前加上arr.reverse();
function binarySearch(argTarget, argArry) {
let isReverse = argArry[0] > argArry[1];
function deal(startIndex, endIndex) {
let middleIndex = ((startIndex + endIndex) / 2) | 0;
let number = argArry[middleIndex];
if (number === argTarget) {
return middleIndex;
} else if (number > argTarget) {
isReverse
? (startIndex = middleIndex + 1)
: (endIndex = middleIndex - 1);
} else {
isReverse
? (endIndex = middleIndex - 1)
: (startIndex = middleIndex + 1);
}
if (startIndex <= endIndex) {
return deal(startIndex, endIndex);
}
}
let index = deal(0, argArry.length - 1);
return index === undefined ? -1 : index;
}
argArry[0] > argArry[1] 当数组长度为1时，结果并不重要，要么匹配返回位置，要么结束匹配。
至于空数组的情况可以归纳为无效输入的场景。
发表评论 (审核通过后显示评论)：