## 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:

(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).

(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).

(let ((half (truncate target 2)))
(dichotomy (lambda (index)
(if (<= (aref vector index) half)
(if (<= half (aref vector (1+ index)))
(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;
}
}
}
``````

}
}