Return to Revisions

You can do this by "squeezing" the array. Suppose you had these inputs::

$$a = \{1, 4, 6, 9, 13, 16\}$$ $$z = 14$$

Obviously, the correct solution is \$(1, 13)\$. We can achieve this by taking the first value (it works fine in reverse as well), and stepping backwards through the array until we hit one of the following conditions:

1. You find the value we're looking for (\$a_{0} + a_{i} = z\$)
2. We reach a range that can never equal \$z\$ with \$a_{0}\$ (e.g. \$i = 3, 1 + 9 = 10 < 14\$)
3. We run into our current index (\$0\$).

In scenario #1, return true. In scenario #2, start squeezing from the left-side using the same rules. In scenario #3, return false.

A quickly jotted down implementation in Python - I am quite confident that you can simplify/condense this if you take a few more minutes to do this.

def squeeze_search(array, target):
    left_index = 0
    right_index = len(array) - 1

    while True:
        right_result = squeeze_right(array, target, left_index, right_index)
        if right_result is not None:
            success, left_index, right_index = right_result
            if success:
                return True
        else:
            return False
        left_result = squeeze_left(array, target, left_index, right_index)
        if left_result is not None:
            success, right_index, left_index = left_result
            if success:
                return True
        else:
            return False


def squeeze_left(array, target, current_index, left_index):
    current_value = array[current_index]
    while left_index < current_index:
        left_value = array[left_index]
        if left_value + current_value == target:
            return (True, current_index, left_index)
        elif left_value + current_value > target:
            return (False, current_index, left_index)

        left_index = left_index + 1

    return None

def squeeze_right(array, target, current_index, right_index):
    current_value = array[current_index]
    while right_index > current_index:
        right_value = array[right_index]
        if right_value + current_value == target:
            return (True, current_index, right_index)
        elif right_value + current_value < target:
            return (False, current_index, right_index)

        right_index = right_index - 1
    return None