CODEWITHSUNDEEP
python
Paschalis
Paschalis

Reputation: 181

Modified(?) binary search

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)

Upvotes: 0

Views: 122

Answers (2)

Patrick Haugh
Patrick Haugh

Reputation: 60944

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.

Upvotes: 0

ksha
ksha

Reputation: 2087

Since you want to do it with Binary Search:

  1. Take unique values from the list and sort
  2. Create an auxiliary list which representing counts of those values.
  3. 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.

Upvotes: 1

Related Questions