Python query in list without for loop

Question

I want to find a sum with pair of numbers in python list.

List is sorted
Need to check consecutive combinations
Avoid using for loop

I used a for loop to get the job done and its working fine. I want to learn other optimized way to get the same result.

Can I get the same result with other ways without using a for loop?

How could I use binary search in this situation?

This is my code:

def query_sum(list, find_sum):
    """
    This function will find sum of two pairs in list
    and return True if sum exist in list
    :param list:
    :param find_sum:
    :return:
    """
    previous = 0
    for number in list:
        sum_value = previous + number
        if sum_value == find_sum:
            print("Yes sum exist with pair {} {}".format(previous, number))
            return True
        previous = number

x = [1, 2, 3, 4, 5]
y = [1, 2, 4, 8, 16]

query_sum(x, 7)
query_sum(y, 3)

this is the result.

Yes sum exist with pair 3 4
Yes sum exist with pair 1 2

What is your definition of loop? Im curious how you plan to go through all the data if you do not visit each element in your arrays. — Fallenreaper, Aug 06 '19 at 02:44
the goal of Python is to make writing code easy and result in clear and easy to read code. there should be one best way to code a given problem. in this case i think you have it. i could code up more complicated ways but that would not really be coding Python. — Skaperen, Aug 06 '19 at 02:47
Possible duplicate of [Find all combinations of a list of numbers with a given sum](https://stackoverflow.com/questions/34517540/find-all-combinations-of-a-list-of-numbers-with-a-given-sum) — Trenton McKinney, Aug 06 '19 at 02:48
@Fallenreaper perhaps OP is expecting there to be a library function to do this or wants to see a comprehension (the complicated way i mentioned above). — Skaperen, Aug 06 '19 at 02:51
It's probably bad form to use an internal `dtype` as the name of your function parameter. /shrug — Trenton McKinney, Aug 06 '19 at 03:43
As the code is written, it's implied that the intent is to only find sequential combinations whose sum is equal to `find_sum`. However, the question is ***find a sum with pair of numbers in python list***. So for clarification, do you want only consecutive combinations or all combinations? — Trenton McKinney, Aug 06 '19 at 04:10
`[seq for seq in itertools.combinations(x, 2) if sum(seq) == find_sum]` probably the most succinct, pythonic implementation to find all combinations. — Trenton McKinney, Aug 06 '19 at 04:39

Mad Physicist · Answer 1 · 2019-08-06T03:32:39.287

You can indeed use binary search if your list is sorted (and you are only looking at sums of successive elements), since the sums will be monotonically increasing as well. In a list of N elements, there are N-1 successive pairs. You can copy and paste any properly implemented binary search algorithm you find online and replace the criteria with the sum of successive elements. For example:

def query_sum(seq, target):
    def bsearch(l, r):
        if r >= l:
            mid = l + (r - l) // 2
            s = sum(seq[mid:mid + 2])
            if s == target:
                return mid
            elif s > target:
                return bsearch(l, mid - 1)
            else:
                return bsearch(mid + 1, r)
        else:
            return -1
    i = bsearch(0, len(seq) - 1)
    if i < 0:
        return False
    print("Sum {} exists with pair {} {}".format(target, *seq[i:i + 2]))
    return True

^{IDEOne Link}

You could use the built-in bisect module, but then you would have to pre-compute the sums. This is a much cheaper method since you only have to compute log₂(N) sums.

Also, this solution avoids looping using recursion, but you might be better off writing a loop like while r >= l: around the logic instead of using recursion:

def query_sum(seq, target):
    def bsearch(l, r):
        while r >= l:
            mid = l + (r - l) // 2
            s = sum(seq[mid:mid + 2])
            if s == target:
                return mid
            elif s > target:
                r = mid - 1
            else:
                l = mid + 1
        return -1
    i = bsearch(0, len(seq) - 1)
    if i < 0:
        return False
    print("Yes sum exist with pair {} {}".format(*seq[i:i + 2]))
    return True

^{IDEOne Link}

@BradSolomon. OP never said anything about sorted. It was just an assumption I made based on him asking about binary search. I don't think your answer needs to be deleted. — Mad Physicist, Aug 06 '19 at 03:29

score 1 · Answer 2 · answered Aug 08 '19 at 03:36

# simpler one:
def query_sum(seq, target):
    def search(seq, index, target):
        if index < len(seq):
            if sum(seq[index:index+2]) == target:
                return index
            else:
                return search(seq, index+1, target)
        else:
            return -1
    return search(seq, 0, target)

Python query in list without for loop

2 Answers2