Have some ideas to improve code from this discussion (Find valid triples for a sorted list of integers) and post new code in a new post.
The new idea is to try to remember where low bound searched last time, and when doing the search, only search from the lower bound where last search is satisfied, since with
j increase each time, the 3rd dimension of satisfied triple could only increase. More specifically, these two lines,
#upperBoundIndex = findSum(numbers, j+1, numbers[i]+numbers[j]) # previous code upperBoundIndex = findSum(numbers, upperBoundIndex, numbers[i] + numbers[j])
I'm working on a problem in which I have an input array, sorted positive unique integers, and have to try to find all possible triples \$(x,y,z)\$ which satisfy \$x+y>z\$ and \$x<y<z\$. For example, \$(1,2,3)\$ is not a valid triple since \$1+2\$ is not \$> 3\$, and \$(3,4,5)\$ is a valid triple since \$3<4<5\$ and \$3+4>5\$.
This code leverages binary search, and I'm wondering if this can be improved in terms of time complexity. Please also help to point out any code issues/bugs or improvement areas.
BTW, I am not using enumeration feature of Python since I want to keep j greater than i, and leverage the feature in my logics.
from __future__ import division def findSum(numbers, startIndex, value): """ find index whose value is less than input parameter value (as upper bound) ,and the greatest possible value possible :param numbers: sorted value to search, may contains duplicates :param startIndex: where to search from, inclusive :param value: upper bound to search :return: the index whose value is less than upper bound value """ low = startIndex high = len(numbers) - 1 while low <= high: mid = (low + high) // 2 if numbers[mid] == value: while mid >= low and numbers[mid] == value: mid -= 1 return mid if mid >= low else -1 elif numbers[mid] > value: high = mid - 1 else: low = mid + 1 # while return low-1 if (low-1) >= startIndex else -1 def findTriagles(numbers): """ :param numbers: could contains duplicate number, assume numbers are sorted :return: unique triples """ results = set() for i in range(0, len(numbers)-2): upperBoundIndex=min(i+2, len(numbers)-1) for j in range(i+1, len(numbers)-1): #upperBoundIndex = findSum(numbers, j+1, numbers[i]+numbers[j]) # previous code upperBoundIndex = findSum(numbers, upperBoundIndex, numbers[i] + numbers[j]) if upperBoundIndex != -1: for k in range(j+1, upperBoundIndex+1): results.add((numbers[i],numbers[j],numbers[k])) return results if __name__ == "__main__": #print findTriagles([4,5,6,7]) # output, set([(4, 6, 7), (4, 5, 7), (4, 5, 6), (5, 6, 7)]) print findTriagles([4, 4, 6, 7]) # output, set([(4, 4, 6), (4, 4, 7), (4, 6, 7)])