[Answered ]-How to apply binary search in python on sorted list of string elements?

by

2👍

✅

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']
👤Martin Evans

0👍

you can use a list comprehension to filter the items you want:

[x for x in cities if x.startswith('New')]
👤scytale

0👍

If you want an implementation of binary search in python, then this might help you.

def binarySearch(alist, item):
    first = 0
    last = len(alist)-1
    found = False

    while first<=last and not found:
         midpoint = (first + last)//2
         if alist[midpoint] == item:
             found = True
         else:
             if item < alist[midpoint]:
                 last = midpoint-1
             else:
                 first = midpoint+1

    return found

testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
print(binarySearch(testlist, 3))    
print(binarySearch(testlist, 13))

source: http://interactivepython.org/runestone/static/pythonds/SortSearch/TheBinarySearch.html

👤Abhi

Leave a comment