1

我有一个 5000 个整数的排序数组。我能以多快的速度判断一个随机整数是否是数组的成员？一般来说，C 和 Ruby 的答案会很好。

数组值的形式为

c * c + 1

其中c可以是 1 到 5000 之间的任何整数。

例如：

[2, 5, 10, 17, 26, 37, 50 ...]
4

9 回答 9

15

log(n) 用于 c 上的二进制搜索

于 2009-01-22T20:06:11.023 回答
10

我会说它是 O(const)！:)

给定一个随机数 r，检查它是否是一个可以用 (n*n+1) 形式表示的数字是很简单的。只需检查 sqrt(r-1) 是否为整数！

（嗯，它可能比这更复杂一点，因为您的编程语言可能会在处理整数与浮点数时引入一些复杂性，但仍然：您根本不需要搜索数组：只需检查数字是否在这种特殊的形式。）

于 2009-01-22T20:20:53.537 回答
6

正如其他人所提到的，二分搜索是 O(log2N)，并且可以递归编码：

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

sqrt(N-1)但是，如果您正在寻找最快的方法，您可以根据您的数字设置一个查找表。只需 5,000 个单词的内存，您就可以通过这种方式实现 O(1) 查找。

解释：

由于对于从 1 到 N 的整数 N，所有数字的形式为 N^2 + 1，因此您可以创建一个包含 N 个元素的表。位置 i 处的元素将指定 i^2 + 1 是否在您的数组中。该表可以用长度为 N 的简单数组来实现。构建需要 O(N) 和 N 个单词的空间。但是一旦你有了表，所有的查找都是 O(1)。

例子：

这是 Python 中的示例代码，读起来像伪代码，一如既往:-)

import math

N = 5000
ar = [17, 26, 37, 50, 10001, 40001]

lookup_table = [0] * N

for val in ar:
    idx = int(math.sqrt(val - 1))
    lookup_table[idx] = 1

def val_exists(val):
    return lookup_table[int(math.sqrt(val - 1))] == 1

print val_exists(37)
print val_exists(65)
print val_exists(40001)
print val_exists(90001)

建表最多占用 O(N)，查找是 O(1)。

于 2009-01-22T20:11:33.743 回答
5

从技术上讲，在固定大小的数组中查找元素的复杂性是恒定的，因为 log 2 5000 不会改变。

于 2009-01-22T20:23:01.287 回答
2

二分查找是 O(log n)

维基百科

于 2009-01-22T20:07:47.667 回答
1

O(log n) 如果数组有 n 个元素

于 2009-01-22T20:07:00.273 回答
1

只是为了扩展：它是lg n测试，即log 2 n。这使它成为O( log n)。为什么？因为二进制搜索的每次尝试都会将数组分成两半；因此需要lg n 次试验。

于 2009-01-22T20:09:22.577 回答
0

使用二分搜索，它是 Log(N) 搜索时间。 

bool ContainsBinarySearch(int[] array, int value) {
  return Array.BinarySearch(arrray, value) >= 0;
}
于 2009-01-22T20:07:11.520 回答
0

在 Perl 中：

我会将这些值加载到静态哈希中，然后它将是 O(1)。

构建查找哈希

lookup_hash{$_} = 1 foreach (@original_array);

查找语法

($lookup_hash{$lookup_value}) && print "Found it in O(1) - no loop here\n";

于 2009-01-22T20:31:46.963 回答