views:

370

answers:

9

I have a sorted array of 5000 integers. How fast can I tell if a random integer is a member of the array? An answer in general, C and Ruby would be nice.

The array values are of the form

c*c+1

where c can be any integer from 1 to 5000

i.e.

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

+14  A: 

log(n) for binary search on c

orip
+1  A: 

O(log n) if the array has n elements

A: 

Using a binary search, it's Log(N) search time.

bool ContainsBinarySearch(int[] array, int value) {
  return Array.BinarySearch(arrray, value) >= 0;
}
JaredPar
+2  A: 

Binary Search is O(log n)

WikiPedia

JoshBerke
+1  A: 

Just to expand on that: it's lg n tests, that is log2 n. That makes it O(log n). Why? because each trial of a binary search divides the array in half; thus it takes lg n trials.

Charlie Martin
+5  A: 

Binary search, as others have mentioned, is O(log2N), and can be coded either recursively:

   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
   }

or iteratively:

   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
   }

However, if you're looking for the fastest possible way, you can set up a look up table based on the sqrt(N-1) of your numbers. With just 5,000 words of memory you can achieve O(1) lookups this way.

Explanation:

Since all your numbers are of the form N^2 + 1 for an integer N from 1 to N, you can create a table of N elements. The element at position i will specify if i^2 + 1 is in your array or not. The table can be implemented with a simple array of length N. It will take O(N) to build, and N words of space. But once you have the table, all lookups are O(1).

Example:

Here's sample code in Python, which reads like pseudocode, as always :-)

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)

Building the table takes up O(N) at most, and lookups are O(1).

Eli Bendersky
Can you elaborate on the O(1) lookups ... this is what I was looking for specifically ...
Auburnate
Elaborated. If you need more details let me know what exactly
Eli Bendersky
Could you post a code snippet in any language that shows how to implement this?
Auburnate
Gladly, here's the python code
Eli Bendersky
Thanks for your time.
Auburnate
+9  A: 

I would say it's O(const)! :)

Given a random number r, it's trivial to check whether it's a number that could be represented in the form (n*n+1). Just check whether the sqrt(r-1) is an integer or not!

(Well, it might be a little more complicated than that since your programming language can introduce some complexity into dealing with integers vs floating point numbers, but still: you do not need to search the array at all: just check whether the number is in this particular form.)

kirillka
if this actually works, and it looks like it should, then you are a genius for figuring this out when everyone else looked at it as a search problem (including me). I wish I could upvote more than once...
rmeador
The OP specifically said in a comment that this is not the solution they're looking for about 1 min after posting the question.
Bill the Lizard
+4  A: 

Technically, the complexity of finding an element in a fixed-size array is constant, since log2 5000 isn't going to change.

Bill the Lizard
A: 

In Perl:

I would load the values into a static hash and then it would be O(1).

Build the Lookup hash

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

Lookup syntax

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

loading the value is O(n)
Greg Dean
Just because the "visible" code is one statement long, that doesn't make the actual lookup O(1). A hash lookup is not a constant-time operation, it's dependent upon the size of the hash and the specific lookup algorithm (not sure which one Perl uses internally).
DanM
DanM - actually, Perl's hashing will be very close to O(1), especially for this amount of elements (i.e. not very large)
Eli Bendersky