Modified(?) binary search

Question

I am trying to solve a problem of finding all the pairs of a list that have a sum of k, in 0(nlogn) time.

I first sort the list (I use merge sort) and then do binary search for each element x of the array to look for (k-x). This works for regular lists, but for example if I have a list like [1,1,1,1] and k=2, my code returns 4 instead of 6. I was wondering if there is any variation of binary search that allows for the above to happen. I tried googling around but I couldn't find anything that covered this question.

For reference this is my code ( I did not include merge sort since it's not relevant)

def binary_search(alist, item):
    if len(alist)==0:
       return False
    else:
       mid=len(alist)//2
       if alist[mid]==item:
          return True
       else:
          if item< alist[mid]:
            return binary_search(alist[:mid], item)
          else:
            return binary_search(alist[mid+1:], item)

def find_pairs(alist, k):
    count=0
    for i in range(len(alist)):
            if binary_search(alist,(k-alist[i])):                        
                    count+=1                       

    return(count)

It sounds like there are two problems here: (1) You want to find all instances of the number you're searching for, rather than just one, so you need to look at the adjacent entries above and below until the value changes, and (2) Once you're doing that, you will then end up double-counting in the case where you have multiple entries whose value is half of the desired sum, so that needs to be accounted for (and if you only have one, then don't count it at all, e.g. if the sum is 2, and you have a single 1, then you cannot form the sum at all). — Tom Karzes
– Tom Karzes, Commented Sep 18, 2018 at 19:03
Your example's output has size O(n^2); you can't even enumerate the solution in O(n lg n) time, let alone find it. — chepner
– chepner, Commented Sep 18, 2018 at 19:06
@chepner The output is a single number. How do you get O(n**2) from that? — Tom Karzes
– Tom Karzes, Commented Sep 18, 2018 at 20:17
@TomKarzes The code isn't trying to compute the number of elements; it's counting them one-by-one. (I also read the first sentence as trying to actually identify each pair, not just count them.) — chepner
– chepner, Commented Sep 19, 2018 at 2:22

ksha · Accepted Answer · 2018-09-18 19:59:26Z

1

Since you want to do it with Binary Search:

Take unique values from the list and sort
Create an auxiliary list which representing counts of those values.
Take first element, mark it x, binary search for (k-x) in the remaining list. If found, add aux[index(x)]*aux[index(k-x)] to result.

Additional step: For the case that you have mentioned, if k is even, look for k/2. If present, add Combination(aux[index(k/2)], 2) to the result.

All this should be within nlogn. Also, you can achieve the same without much hassle using Python Dictionaries.

edited Sep 18, 2018 at 19:59

answered Sep 18, 2018 at 19:43

ksha

2,0871 gold badge20 silver badges23 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Patrick Haugh · Accepted Answer · 2018-09-18 20:20:39Z

0

I think you can do this in O(n) time and O(n) space.

def num_pairs(arr, k):
    counts = Counter(arr)
    total = 0
    for item, count in counts.items():
        diff = k - item
        if diff in counts and (diff < item or (diff==item and count>1)):
            if diff == item:
                total += (count*(count-1))//2
            else:
                total += count*counts[diff]
    return total

Here we make a mapping of each number to the number of times it occurs in the input. For each entry we look up the complement in mapping, and can then compute the number of such pairs using arithmetic.

answered Sep 18, 2018 at 20:20

Patrick Haugh

61.3k13 gold badges94 silver badges101 bronze badges

1 Comment

Paschalis Over a year ago

Thank you so much for the answer. I did something similar that was O(n) but I was asked to do it in O(nlogn) just for purpose of the meeting, that's why I'm asking! :)

Collectives™ on Stack Overflow

Modified(?) binary search

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related