## 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.

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