数组中的二进制搜索

由于这是二进制搜索的关键，因此请确保对数组进行排序。

任何索引/随机访问数据结构都可以进行二进制搜索。因此，当您说使用“只是一个数组”时，我会说数组是采用二进制搜索的最基本/最常见的数据结构。

您可以递归（最简单）或迭代地进行。二进制搜索的时间复杂度为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       elsereturn mid // found   }   return -1 // not found}