how to apply binary search in python on sorted list of string elements?
Question: I have a sorted list of string elements(names of cities) and I would like to
implement binary search on this and filter out cities by giving initial
letters?

for example input by user: <http://127.0.0.1:8000/api/?city=New>

So here in this case I need to find out cities starting from New

Sample Output:

    
    
    [
    "New Abbey|Ceredigion|United Kingdom",
    "New Albany|Indiana|United States",
    "New Albany|Kansas|United States",
    "New Albany|Mississippi|United States",
    "New Albany|Ohio|United States"
    ]
    

Please advise.


Answer: The following approach should work. It uses Python's own binary search library
called `bisect` to find the initial index into you list. For the search term
`New` it returns 2 for my example list. `itertools.takewhile` can then be used
to return entries until your search term fails:

    
    
    import bisect, itertools
    
    locations = [
        "Aaaa|aaaa|Test",
        "Bbbb|bbbb|Test",
        "New Abbey|Ceredigion|United Kingdom",
        "New Albany|Indiana|United States",
        "New Albany|Kansas|United States",
        "New Albany|Mississippi|United States",
        "New Albany|Ohio|United States",
        "Zzzz|zzzz|Test"
        ]
    
    search = "New"
    start_index = bisect.bisect_left(locations, search)
    print list(itertools.takewhile(lambda x: x.startswith(search), itertools.islice(locations, start_index, None)))
    

Giving the following output:

    
    
    ['New Abbey|Ceredigion|United Kingdom', 'New Albany|Indiana|United States', 'New Albany|Kansas|United States', 'New Albany|Mississippi|United States', 'New Albany|Ohio|United States']
    

