## Consecutive Array Search

### January 10, 2020

If the array is unsorted, there is no better algorithm than linear search through the array:

(define (f x xs) ; unsorted (let loop ((xs xs)) (cond ((or (null? xs) (null? (cdr xs))) (list)) ((= (+ (car xs) (cadr xs)) x) (list (car xs) (cadr xs))) (else (loop (cdr xs))))))

> (f 7 '(4 6 2 5 1 3 7)) (2 5)

> (f 7 '(4 6 5 1 2 3 7)) ()

If the array is sorted, use binary search to find the largest number smaller than half the target:

(define (f x xs) ; sorted (let ((i (bsearch < (quotient x 2) xs))) (if (and i (= (+ (vector-ref xs i) (vector-ref xs (+ i 1))) x)) (list (vector-ref xs i) (vector-ref xs (+ i 1))) (list))))

> (f 7 '#(1 2 3 4 5 6 7)) (3 4)

> (f 6 '#(1 2 3 4 5 6 7)) ()

You can run the program at https://ideone.com/tXaz0S, where you can also see the binary search code.

In Python. It uses a lazy array with the sums of the consecutive elements, so that for the sorted array case we can search for the target.

public class Main {

public static void main(String args[])

{

int target = 100;

int[] numeros = {5, 26, 39, 47, 53, 38, 12, 23, 41, 39, 40, 16, 47, 13, 10, 18, 4, 22, 50};

}

}