Consecutive Array Search

January 10, 2020

Given an array of distinct integers and a target integer, determine if two adjacent integers in the array sum to the target. Solve the problem twice, once assuming the array is unsorted and once assuming the array is sorted.

Your task is to solve the two array search problems described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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: