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};
}
}
Here’s a solution in C.
The program takes a target value, followed by a u or s (to indicate sorted or unsorted), followed by an array of ints.
The printed output shows the index of the first element of the pair of adjacent elements that sum to the specified target. If there is no such pair, the program prints -1.
Example usage: