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

### 4 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;
}
}
}
``````

}
}

4. Daniel said

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.

```#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

int search(int* array, int n, int target) {
for (int i = 0; i < n - 1; ++i) {
if (array[i] + array[i + 1] == target)
return i;
}
return -1;
}

int search_sorted(int* array, int n, int target) {
int bound = (target >> 1) + (target & 1);
int lo = 0;
int hi = n;
int idx = -1;
while (hi > lo) {
int mid = lo + ((hi - lo) >> 1);
int val = array[mid];
if (val < bound) {
idx = mid;
lo = mid + 1;
} else {
hi = mid;
}
}
if (idx > -1
&& idx + 1 < n
&& array[idx] + array[idx + 1] == target)
return idx;
return -1;
}

int main(int argc, char* argv[]) {
assert(argc >= 3);
int target = atoi(argv);
char c = argv;
assert(c == 'u' || c == 's');
int sorted = c == 's';
int n = argc - 3;
int* array = malloc(sizeof(int) * n);
for (int i = 0; i < n; ++i) {
array[i] = atoi(argv[i + 3]);
}
int idx;
if (sorted) {
idx = search_sorted(array, n, target);
} else {
idx = search(array, n, target);
}
printf("%d\n", idx);
free(array);
return EXIT_SUCCESS;
}
```

Example usage:

```\$ ./a.out 7 u 4 6 2 5 1 3 7
2

\$ ./a.out 7 u 4 6 5 1 2 3 7
-1

\$ ./a.out 7 u 1 2 3 4 5 6 7
2

\$ ./a.out 6 u 1 2 3 4 5 6 7
-1
```