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.
;; When the vector is not sorted, we must use a simple sequential search: (defun contains-adjacent-sum-p (target vector) (loop :for i :below (1- (length vector)) :thereis (= target (+ (aref vector i) (aref vector (+ i 1)))))) (assert (contains-adjacent-sum-p 33 #(1 33 44 11 22 0 33))) (assert (not (contains-adjacent-sum-p 33 #(1 33 44 11 23 0 32)))) ;; When the vector is sorted, we can still use a simple sequential ;; search, but we may stop searching as soon as the element in the ;; vector is greater than half the target (since then, adding it to ;; the next element will give more than the target). (defun contains-adjacent-sum-p/sorted (target vector) (loop :with half := (truncate target 2) :for i :below (1- (length vector)) :while (<= (aref vector i) half) :thereis (= target (+ (aref vector i) (aref vector (+ i 1)))))) (assert (contains-adjacent-sum-p/sorted 33 #(0 1 11 22 33 33 44))) (assert (not (contains-adjacent-sum-p/sorted 33 #(0 1 11 23 32 33 44)))) ;; However, this is still O(n). We can do better, noticing that ;; if target=a[i]+a[i+1] with a[i]<=a[i+1] ;; then we must have a[i]<=target/2 and target/2<=a[i+1] ;; If target/2<a[i] then target<2*a[i]<=a[i]+a[i+1] ;; If a[i+1]<target/2 then a[i]+a[i+1]<=2*a[i+1]<target ;; Therefore we can perform a dichotomy search, and obtain the result in log₂(n). (defun contains-adjacent-sum-p/sorted/logn (target vector) (let ((half (truncate target 2))) (dichotomy (lambda (index) (if (<= (aref vector index) half) (if (<= half (aref vector (1+ index))) (return-from contains-adjacent-sum-p/sorted/logn (when (= target (+ (aref vector index) (aref vector (1+ index)))) index)) +1) -1)) 0 (1- (length vector))) nil)) (assert (contains-adjacent-sum-p/sorted/logn 33 #(0 1 11 22 33 33 44))) (assert (not (contains-adjacent-sum-p/sorted/logn 33 #(0 1 11 23 32 33 44))))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.
from bisect import bisect_left def bsearch(arr, x): ind = bisect_left(arr, x) if ind != len(arr) and arr[ind] == x: return ind return -1 class SummedArr(object): """Lazy sums of pairs of arr""" def __init__(self, arr): self.arr = arr def __getitem__(self, i): return self.arr[i] + self.arr[i+1] def __len__(self): return len(self.arr) - 1 def unsorted_arr(arr, target): for i, e in enumerate(SummedArr(arr)): if e == target: return arr[i], arr[i+1] return False def sorted_arr(arr, target): ind = bsearch(SummedArr(arr), target) if ind != -1: return arr[ind], arr[ind+1] return False arr = [5, 26, 39, 47, 53, 38, 12, 23, 41, 39, 40, 16, 47, 13, 10, 18, 4, 22, 50] print(unsorted_arr(arr, 100)) #-> (47, 53) print(unsorted_arr(sorted(arr), 100)) # False print(sorted_arr(sorted(arr), 100)) # False arr = [5, 26, 39, 47, 53, 38, 12, 23, 41, 39, 40, 16, 47, 13, 10, 18, 4, 22] print(unsorted_arr(arr, 100)) #-> (47, 53) print(unsorted_arr(sorted(arr), 100)) #-> (47, 53) print(sorted_arr(sorted(arr), 100)) #-> (47, 53)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};
}
}