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
– Fallenreaper, Commented Aug 6, 2019 at 2: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
– Skaperen, Commented Aug 6, 2019 at 2:47
Possible duplicate of Find all combinations of a list of numbers with a given sum — Trenton McKinney
– Trenton McKinney, Commented Aug 6, 2019 at 2: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
– Skaperen, Commented Aug 6, 2019 at 2:51
It's probably bad form to use an internal dtype as the name of your function parameter. /shrug — Trenton McKinney
– Trenton McKinney, Commented Aug 6, 2019 at 3:43

Mad Physicist · Accepted Answer · 2019-08-06 03:32:39Z

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.

Saeid Gholizade · Accepted Answer · 2019-08-08 03:36:00Z

1

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

answered Aug 8, 2019 at 3:36

Saeid Gholizade

898 bronze badges

Collectives™ on Stack Overflow

Python query in list without for loop

2 Answers 2

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related