二进制搜索寻找魔术索引

我正在练习二进制搜索，当我尝试实现它来查找数组中的“魔术索引”时，我正在碰壁。神奇指数是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。

来源

2017-04-04 Jose

您没有提及该数组是排序的 – MBo

@MBo我不确定您是否试图从OP中确认他的数组是否已排序，但是如果没有，则二分查找假设排序，不是吗？ – 0xc0de

@Jose，二进制搜索仅适用于已排序的数组，第二个数组未进行排序。 – 0xc0de

既然你在练习，我认为你自己编码对你有好处，但我会给你一个指导。

使用此算法（注意输入数组应该已经被排序，否则实行分类法）：

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，如果关键是没有找到。

来源

2017-04-04 04:02:57

这个算法不会找到一个'魔术指数'，会吗？ OP解决方案中的逻辑对我来说似乎是正确的。 – 0xc0de

只需将键设置为预期的索引。该算法用于通用目的; m←floor（（l + r）/ 2）; K←m;' –

什么是'意向指数'？事实上，这里不需要'K'，只需'm == arr [m]'即可。我指出，因为OP的算法没有问题。 – 0xc0de

您的第二个数组未被排序，并且binary search仅适用于已排序的数组。

来源

2017-04-04 05:26:39 0xc0de

谢谢，当在控制台中进行沙盒操作时，我必须保持负面信号。 – Jose

二进制搜索寻找魔术索引

回答

相关问题