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.
Programming Praxis 
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 Nonejust do binary search for the first n elements which will be in logarthimic time