数组中的二进制搜索

Question

如何仅使用数组实现二进制搜索？

Answer 1

确保您的数组已排序,因为这是二进制搜索的关键.

可以二进制搜索任何索引/随机访问数据结构.所以当你说"只是一个数组"时,我会说数组是采用二进制搜索的最基本/最常见的数据结构.

您可以递归(最简单)或迭代地执行此操作.二进制搜索的时间复杂度是O(log N),这比在O(N)处检查每个元素的线性搜索快得多.以下是维基百科的一些示例:二进制搜索算法:

递归:

BinarySearch(A[0..N-1], value, low, high) {  
    if (high < low)  
        return -1 // not found  
    mid = low + ((high - low) / 2) 
    if (A[mid] > value)  
        return BinarySearch(A, value, low, mid-1)  
    else if (A[mid] < value)  
        return BinarySearch(A, value, mid+1, high)  
    else
       return mid // found
    }

迭代:

  BinarySearch(A[0..N-1], value) {
   low = 0
   high = N - 1
   while (low <= high) {
       mid = low + ((high - low) / 2)
       if (A[mid] > value)
           high = mid - 1
       else if (A[mid] < value)
           low = mid + 1
       else
           return mid // found
   }
   return -1 // not found
}