二进制搜索寻找魔术索引
问题描述:
我正在练习二进制搜索,当我尝试实现它来查找数组中的“魔术索引”时,我正在碰壁。神奇指数是A[i] == i
。二进制搜索寻找魔术索引
我在Java using recursion中发现了一些实现,但我试图避免这样做递归,因为递归是昂贵的(我想看看二进制搜索是否适合在这里)。
这里是我的代码:
function magicIndex(arr) {
var result = arr, mid;
while (result.length > 1) {
mid = Math.floor(result.length/2);
if (result[mid] === mid) {
return arr.indexOf(result[mid]);
} else if (mid > result[mid]) {
result = result.slice(mid+1, result.length);
} else {
result = result.slice(0, mid);
}
}
return arr.indexOf(result.pop());
}
的问题是,该算法不正确切片中的某些测试运行的阵列到反面。
例如,[-10, -3, 0, 2, 4, 8]
返回4
,但[-10, 1, 0, 2, 5, 8]
也返回4
。
答
既然你在练习,我认为你自己编码对你有好处,但我会给你一个指导。
使用此算法(注意输入数组应该已经被排序,否则实行分类法):
int arr[n];
K ← 1; //search key
l ← 0; r ← n - 1;
while l ≤ r do
m ← floor((l + r)/2)
if K = arr[m]
return m
else if K < arr[m]
r ← m − 1
else
l ← m + 1
return −1
这将输出你的搜索键的索引,-1,如果关键是没有找到。
您没有提及该数组是排序的 – MBo
@MBo我不确定您是否试图从OP中确认他的数组是否已排序,但是如果没有,则二分查找假设排序,不是吗? – 0xc0de
@Jose,二进制搜索仅适用于已排序的数组,第二个数组未进行排序。 – 0xc0de