Searching An Infinite Array

December 9, 2016

First we need a way to create an infinite array in ascending order. Function (next n x) returns the next n items from an array, starting from x, by adding a random integer from 1 to 5 to the current array element:

(define gap 5)
(define (next n x)
  (let loop ((n (- n 1)) (xs (list (+ x (randint gap) 1))))
    (if (zero? n) (list->vector (reverse xs))
      (loop (- n 1) (cons (+ (car xs) (randint gap) 1) xs)))))

Now we can perform the search. We begin with the first item in the array, then the next two, then the next four, and so on, with each sub-array growing by the next power-of-two, until the last integer in the array is greater than or equal to the target, at which time we perform binary search in the most recent sub-array:

(define (search k)
  (let loop ((base 0) (two 2) (ary (next 1 0)))
    (display ary) (newline)
    (let ((x (vector-ref ary (- (vector-length ary) 1))))
      (if (< x k)
          (loop (+ base (/ two 2)) (* two 2) (next two x))
          (let ((idx (bsearch < k ary)))
            (if idx (+ base idx) #f))))))

Here base is the index of the first integer in the current sub-array and two is the length of the next sub-array. We left in debugging code that shows the successive sub-arrays, so you can see that the function works properly. Our bsearch is shown below:

(define (bsearch lt? x xs)
  (let loop ((lo 0) (hi (- (vector-length xs) 1)))
    (let ((mid (quotient (+ lo hi) 2)))
      (cond ((< hi lo) #f)
            ((lt? x (vector-ref xs mid))
              (loop lo (- mid 1)))
            ((lt? (vector-ref xs mid) x)
              (loop (+ mid 1) hi))
            (else mid)))))

Since we chose a gap of 5, on average we will find k in one search out of five:

> (search 79)
#(5)
#(10 15)
#(17 18 22 24)
#(29 31 33 38 41 45 50 54)
#(59 63 64 69 71 75 76 77 82 86 90 91 96 100 103 104)
#f
> (search 79)
#(3)
#(7 12)
#(17 19 24 29)
#(32 33 36 41 46 50 51 55)
#(56 60 63 64 66 71 73 76 81 84 89 91 93 96 99 102)
#f
> (search 79)
#(4)
#(7 9)
#(12 13 16 19)
#(20 21 24 25 30 35 38 39)
#(44 46 50 53 57 61 64 67 68 69 72 76 79 82 84 87)
27
> (search 79)
#(2)
#(7 12)
#(16 17 18 23)
#(24 29 33 34 36 37 39 44)
#(45 49 52 54 59 60 63 67 70 72 77 82 83 87 88 92)
#f
> (search 79)
#(1)
#(2 7)
#(12 17 19 20)
#(21 22 23 27 31 34 39 43)
#(45 49 51 55 58 59 62 63 66 67 68 70 72 76 80 83)
#f

We used the random number generator from the Standard Prelude. You can run the program at http://ideone.com/yIXP5W.

Advertisements

Pages: 1 2

2 Responses to “Searching An Infinite Array”

  1. Paul said

    A solution in Python

    def search(iterable, x):
        section = [next(iterable)]
        n = 1
        while section[-1] < x:
            n *= 2
            section = list(islice(iterable, n))
        ind = bisect.bisect_left(section, x)
        return ind + n - 1 if section[ind] == x else None
    
  2. xvanger said

    just do binary search for the first n elements which will be in logarthimic time

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: