Binary search to identify duplicate user names

Question

I am trying to implement the code described this post about how Reddit identifies duplicate user names (I do believe it is called binary search). Just to clarify, this is mainly for me figuring out how these things work; thanks @Graipher for pointing to bisect). The way I understand it, the steps are:

1. You have a new user name you are comparing to an alphabetically sorted list of existing names

2. You compare that new name to the middle item in the list.

3. If there is no match, you check if the new name is higher or lower in the alphabet than the middle item, and focus on this side of the list, again checking the middle item.

4. You repeat until there is a match ("User name taken") or none ("User name available").

Below is what I have. It seems to work when I test it on the names in the list and random other names. It'd cool if someone had some feedback re:

• Will this work correctly or is there some kind of bug?

• Is the while loop the right way to go? Are there better options? I especially don't like the separate loop for a list of length 1.

• Performance-wise, are there any real hiccups in here?

• Any other comments are much appreciated!

-

def checker(new_name, old_names):
    """
    The checker takes a string new_name and checks if it is contained in the list old_names.
    It prints out the results.
    """ 
    print "***\n\ninitializing the checker"
    print "searching for ", new_name
    print "old names", old_names
    old_names= sorted(old_names)
    #set the match variable to false
    namematch= False
    #iterate over list while new_name does not match
    while not namematch and len(old_names) > 1:
        middle= len(old_names)/2
        print "middle item is", old_names[middle], "middle index is", middle
        #match
        if old_names[middle] == new_name:
            namematch= True
        #no match
        else:
            if sorted(list((new_name, old_names[middle])))[0] != new_name:
                print "word is to the right"
                old_names = old_names[middle:]
            else:
                print "word is to the left"
                old_names = old_names[:middle]
    #check for list of length 1: is it new_name
    if (len(old_names)) == 1 and (old_names[0] == new_name):
        namematch = True
    if not namematch: 
        print "this name is not taken", new_name
    else:
        print "this name is taken:", new_name

Here is my test data:

-

names_list= [u'annie', u'max', u'chris', u'11alpha', u'zotti', u'zatti', u'zutti', u'?andy', u'getr\xfc', u'zilly']

checker('max', names_list)  # True
checker('fail', names_list)  # False

Answer 1

The description you are providing and your implementation do correspond to binary search indeed. As such, it would probably make sense to perform a few cosmetic changes to your function to make this cleaner and easier to (re)use:

• call it binary_search (or something like that)
• makes the signature (parameter names and documentation) more generic and not based on the concept of name. The parameters could be called item/element/x/needle and sorted_list/sorted_array.
• make the return value clearer, for instance a boolean value telling whether the value was found or not (or maybe an index giving the position)
• move all the input/output logic (except maybe for the debug statements) out of the function.

As for the performances, I am a bit concerned by the fact that you are actually performing copies by using the [:] sublist notation. Thus, each step of the algorithm, instead of operating in constant times will be bigger if the sublist you are copying gets bigger. Also, you are re-sorting the whole array everytime the function is called (and even more that this apparently). The point of using binary search is that you pay the cost of sorting (O(n*log(n))) upfront assuming you'll amortize it by performing many searches in O(log(n)) times. If you have to re-sort everytime, you might as well use a linear search iterating through the array and stopping when the element is found.

Answer 2

In general it does not make sense to roll your own, if there already is a built-in solution. In this case there is the bisect module, which has a method bisect.bisect_left which returns the index where you would have to insert an item to maintain the sorted order.

All you have to do is check if in that position there is already the user name you are checking:

from bisect import bisect_left

old_names = sorted(db_query(...))

def user_name_exists(new_name, old_names):
    return old_names[bisect_left(old_names, new_name)] == new_name

Note that this assumes that your names list is already sorted and that you get the list of old users via some function db_query.

Alternatively, you could use a set. x in set is \$mathcal{O}(1)\$ and uses binary search in the background to see if the hash is already in the set (thanks to @kyrill for suggesting sets in the comments):

old_names = set(db_query(...))

def user_name_exists(new_name, old_names):
    return new_name in old_names