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.

Pages: 1 2

3 Responses to “Consecutive Array Search”

  1. informatimago said
    
    ;; 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))))
    
    
    
  2. Paul said

    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)
    
  3. erick said

    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};

       for (int i = 0; i < numeros.length; i++) {
    
           if (numeros[i] > target || ((i + 1) < numeros.length && numeros[i+1] > target) ) { continue; }
    
           if ((i + 1) < numeros.length) {
               int current = numeros[i];
               int next = numeros[i+1];
               if ((next+current) == target) {
                   System.out.println( current + " + "+next +"  = " + (current + next));
                   break;
               }
           }
       }
    

    }
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: