数组中的二分搜索 [英] Binary Search in Array

问题描述

如何仅使用数组实现二分查找?

How would I implement a binary search using just an array?

推荐答案

确保您的数组已排序，因为这是二分查找的关键.

Ensure that your array is sorted since this is the crux of a binary search.

任何索引/随机访问数据结构都可以进行二分搜索.因此，当您说仅使用数组"时，我会说数组是使用二分搜索的最基本/常见的数据结构.

Any indexed/random-access data structure can be binary searched. So when you say using "just an array", I would say arrays are the most basic/common data structure that a binary search is employed on.

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

You can do it recursively (easiest) or iteratively. Time complexity of a binary search is O(log N) which is considerably faster than a linear search of checking each element at O(N). Here are some examples from Wikipedia: Binary Search Algorithm:

递归:

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
}

这篇关于数组中的二分搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！