Find valid triples for a sorted list of integers (part 2)

Question

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

Answer 1

(I won't comment on the actual algorithm, just on the coding style.)

Overall, this feels pretty ok and standard Python style.

Some remarks:

• remove commented-out code before going "live" (live here meaning, submitting to CR).

• make sure your lines don't exceed 80 characters.
  That will have the added convenience that there'll likely be no horizontal scrollbar for the code block here, making things overall easier to read.

• I like the from __future__ import division, especially since the only division in the code is actually integer divison, and now is explicit with //. Bonus: add from __future__ import print_function, add parentheses to yourprint` statement at the bottom and your code will be "generic" Python, not major version 2 or 3 specific.
  (My preferred approach is to code Python 3, and then if necessary, refactor things to be Python 2 compatible. Start from the future, not from the past.)

• the lower-first-CamelCase style is not Pythonic. CamelCase is used for classes, but functions and variable names are usually all lower case, with underscores as deemed necessary for readability. (NB: you probably want to use the word "triangles", with an "n" in there, instead of "triagles". Or use e.g. find_triplets, since that's in your doc-string description.)

• the quadruple nesting in findTriagles is about the limit of nesting (for-loop within an if-statement within a for-loop within a for-loop), but since the function is really short, it's probably ok. When there's a lot more code in any of these indented parts, consider moving a part to a separate function.

• There is no general document doc-string (describing the purpose of the code), and the doc-string for findTriagles is missing its initial line/sentence: it jumps straight into the parameter description. findSum does this better.

• findSum is an odd name: I don't see any sum calculation there. find_max_index or similar might be better.

• for consistency: add space around the equal sign in upperBoundIndex=min(i+2, len(numbers)-1).