CODEWITHSUNDEEP
pythonpython-3.xlistbinary-search
Rajiv Sharma
Rajiv Sharma

Reputation: 7112

Python query in list without for loop

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

  1. List is sorted
  2. Need to check consecutive combinations
  3. 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

Upvotes: 2

Views: 2711

Answers (2)

Saeid Gholizade
Saeid Gholizade

Reputation: 89

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

Upvotes: 1

Mad Physicist
Mad Physicist

Reputation: 114230

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 log2(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

Upvotes: 2

Related Questions