确定值是否在排序数组中的时间是多少？

Question

我有一个5000整数的排序数组.如果随机整数是数组的成员,我能判断多快？一般来说,C和Ruby会很好.

数组值的形式

c * c + 1

where c可以是1到5000之间的任何整数.

例如:

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

Answer 1

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

Answer 2

我会说它是O(常数)!:)

给定一个随机数r,检查它是否是一个可以表格形式表示的数字(n*n + 1)是微不足道的.只需检查sqrt(r-1)是否为整数!

(好吧,它可能比这复杂一点,因为你的编程语言会在处理整数与浮点数时引入一些复杂性,但仍然:你根本不需要搜索数组:只需检查数字是否在这个特殊的形式.)

Answer 3

正如其他人所提到的,二进制搜索是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)您的数字设置查找表.只需5000字的内存就可以通过这种方式实现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).

Answer 4

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