How to implement binary search to find the index of an item which is inside a list of dictionaries

Question

I have a list containing dictionaries:

base = [
    {"name": "Earth", "Density": 5.427},
    {"name": "Mars", "Density": 5.513},
    {"name": "Venus", "Density": 5.204},
]
name = input("What planet are you looking for? ")

The function should return the index of an item(planet in this case) or -1 if it doesn't exist.

F.e | For input= Earth, expected output would be: 0
For input = venus, expected output: 2

The binary search is a must-have in this task. I am not even giving u my code because it do not even work. I know how binary search works, but no idea how to use it in list of dictionaries. PS. You dont have to write the whole code, just help me how to implement biarny search into list of dictionaries.

That list is not ordered neither by name, nor by density. Binary search is thus not applicable to it. — tevemadar, Dec 10 '20 at 12:35
Yeah, i did not notice. What if it would be sorted by name? {"name": "Earth", "Density": 5.427}, {"name": "Mars", "Density": 5.513}, {"name": "Venus", "Density": 5.204}, — randomobject123, Dec 10 '20 at 12:36
Then it would be possible to do a binary search on names (but not on density) — tevemadar, Dec 10 '20 at 12:37
See https://stackoverflow.com/questions/9501337/binary-search-algorithm-in-python for implementation (just you would use `array[mid]["name"]` for the comparisons). And https://stackoverflow.com/questions/212358/binary-search-bisection-in-python for built-in solution which may be applicable too. — tevemadar, Dec 10 '20 at 12:40
You said you are not showing your code because it doesn't work, but that's what people do on Stack Overflow, help fix broken code :) so please add it to your question. — Tony, Dec 10 '20 at 14:29

score 0 · Answer 1 · answered Dec 10 '20 at 14:20

For each iteration of a binary search it simply halves the number of items you need to check, so it it doesn't really matter if you are traversing a tree or searching a list.

And it doesn't matter if the data being searched is a list of simple integers, dictionaries, or complex objects - it's the comparison function's job to work if you need to choose the "left" or "right" part for the next binary chop.

In your case you'll be finding the middle index of the array, getting the dictionary at that position and comparing the name attribute to what you are looking for. If the item does not match use recursion to pass the left or right half of the list in to the same search function.

Here's an implementation of a recursive binary search algorithm.

Mr. Hobo · Answer 2 · 2020-12-10T12:47:51.987

This will solve your problem:

for idx, value in enumerate(base):
    if value["name"] == name:
        print(idx + 1) # check this
        break

However, I would like to remind you that indexing in python starts at 0, however, for planet Earth you have set 1 as the value. So you should check the indexing.

Converting the same into a function would be like:

def findPlanet(base, name):
    _idx = -1
    for idx, value in enumerate(base):
        if value["name"] == name:
            _idx = idx + 1
            break
        
    return _idx

print(findPlanet(base, "Earth"))
>> 1

print(findPlanet(base, "None"))
>> -1

This is a linear search. OP says a binary search is a must-have. Clearly an assignment of some sort. — BoarGules, Dec 10 '20 at 12:58

How to implement binary search to find the index of an item which is inside a list of dictionaries

2 Answers2