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.

I think the link is supposed to be an example of input - looks like the OP's code extracts "New" from the url — scytale
– scytale, Commented Aug 24, 2015 at 11:37
import bisect --> look here: docs.python.org/3/library/bisect.html#module-bisect :) — Reblochon Masque
– Reblochon Masque, Commented Aug 24, 2015 at 12:01

Martin Evans · Accepted Answer · 2015-08-24 12:25:01Z

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

edited Aug 24, 2015 at 12:25

answered Aug 24, 2015 at 12:13

Martin Evans

46.9k17 gold badges88 silver badges104 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Sanchit Over a year ago

Thanks a lot Martin :)

scytale · Accepted Answer · 2015-08-24 11:32:32Z

0

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

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

answered Aug 24, 2015 at 11:32

scytale

12.7k4 gold badges35 silver badges46 bronze badges

5 Comments

Sanchit Over a year ago

That I've already done but my boss wants me to implement binary search.

scytale Over a year ago

that's incomprehensible. please don't dump code in comments.

scytale Over a year ago

you asked how to find cities starting with new - the answer does that. now you are asking about binary search - which is a very different thing - I think your boss may be confused

Sanchit Over a year ago

I already gave him two solutions, one using list comprehensions and one with the help of regular expression, but he says implement binary search on this which will decrease the search time. Currently it is an iterative search, if we implement binary search then time of searching cities shall reduce.

scytale Over a year ago

well... maybe. you'd want to have a really really bit list of cities for this to be a good use of your time.

Abhi · Accepted Answer · 2015-08-24 11:39:51Z

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

answered Aug 24, 2015 at 11:39

Abhi

5521 gold badge10 silver badges24 bronze badges

Collectives™ on Stack Overflow

how to apply binary search in python on sorted list of string elements?

3 Answers 3

1 Comment

5 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

5 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related