如果找不到搜索值,二分查找如何工作?
例如,如果您要在此数组中搜索 60:
ANDMarks = {1, 6, 38, 39, 45, 55, 57, 61, 72, 73, 88, 96}
结局如何?我试运行了代码,直到搜索到索引 6 和 7。为了更容易得到我要问的内容,这是我的试运行:
步骤:
1.找到中间值。
Middle value = (index of 1st element + index of last element)/2
Middle value = (0+11)/2
Middle value = 5
Middle value = element in 5th index => 55
Indexes 0 1 2 3 4 **5** 6 7 8 9 10 11
Elements 1 6 38 39 45 **55** 57 61 72 73 88 96
第 2 步。中间值 (55) != 60
步骤 3. 中间值 < 搜索值 (55 < 60)
考虑数组中位于中间值之后的部分
Indexes 6 7 8 9 10 11
Elements 57 61 72 73 88 96
第 4 步。
Middle value = (index of 1st element + index of last element)/2
Middle value = (6+11)/2
Middle value = 8
Middle value = element in 8th index => 72
Indexes 6 7 **8** 9 10 11
Elements 57 61 **72** 73 88 96
第 5 步。中间值 (72) != 60
第 6 步. 中间值 > 搜索值 (72 > 60)
考虑数组中位于中间值之前的部分。
Indexes 6 7
Elements 57 61
现在发生了什么?
最佳答案
我知道我来晚了,您现在可能已经弄明白了,但是尽管如此,这个问题有超过 5000 次浏览,但没有明确的解释。
也许我的解释可以帮助任何有抱负的计算机科学爱好者。
Here is my explanation目前,我在堆栈溢出方面没有足够的声誉,所以它不允许我嵌入图像。请随时检查解释,因为它包含图像。
如果有人喜欢或同意,请随时竖起大拇指,因为这会鼓励我在 Stack Overflow 上留下更多回复和帖子。
下面是我的 JavaScript 代码,你可以在 Chrome 开发者工具中复制粘贴,调试它,看看它是如何工作的。
function binarySearch(arr, val) {
let mid = Math.floor(arr.length / 2);
let left = 0;
let right = arr.length - 1;
while (arr[mid] !== val && ((left != mid) && (mid != right))) {
if (val > arr[mid]) {
left = mid + 1;
mid = Math.floor((left + right) / 2);
} else if (val < arr[mid]) {
right = mid - 1;
mid = Math.floor((left + right) / 2);
}
}
return arr[mid] === val ? mid : -1;
}
arr1 = [3, 7, 9, 11, 12, 14, 20]
console.log(binarySearch(arr1, 14));
console.log(binarySearch(arr1, 1));
console.log(binarySearch(arr1, 23));
console.log(binarySearch(arr1, 8));
console.log(binarySearch(arr1, 16));
编码愉快!
关于binary-search - 如果找不到搜索值,二分查找如何工作?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22374248/