0

I have a list of lists which contain a set of postcodes and the suburbs that match with. I need to create a iterative binary search algorithm that asks the user to input the name of the suburb and then the program outputs the postcode the suburb belongs to. The list looks like this:

L = [['4000', 'Charlestown'], ['4001', 'Jamestown'], ['4002', 'Henrytown']]

So if I were to run a binary search on this and the user entered 'Jamestown', then the program would output '4001'. This is what I've done to create the binary search function: 

    suburb = input("Please enter the name of a suburb: ")

    def binarySearch(L, target):
        low = 0
        high = len(L)-1
        while low <= high:
            mid = (low + high)//2
            if L[mid] == target:
                return mid
            elif L[mid] > target:
                high = mid-1
            else:
                low = mid+1
    binarySearch(L, suburb)

However, when I run the program I get an error:

elif L[mid] > target:

TypeError: '>' not supported between instances of 'list' and 'str'

I'm not really sure how to resolve this problem, any help would be greatly appreciated. Thanks!

m0nhawk
  • 22,980
  • 9
  • 45
  • 73
Henry Jones
  • 19
  • 2

5 Answers5

1

Just use a dictionary for this. Makes life much easier:

>>> d = {key: val for (val, key) in L}
>>> d['Jamestown']
'4001'
MrLeeh
  • 5,321
  • 6
  • 33
  • 51
1

For this kind of problem, you're going to be better off if you can structure the data as a dictionary, e.g.,:

zips = { 'Charlestown': 4000, 'Jamestown': 4001,'Henrytown': 4002}

then you can look up the zip code for any suburb in one step:

zips['Charlestown']

will evaluate to:

4000

If you have a bunch of these to look up, and for some reason the data was given to you in a list, you can convert from a list to a dictionary. That question is answered nicely here:

Convert a list to a dictionary in Python

If you are being forced to do work with an odd data structure for an exercise for homework, see my separate answer for you below.

Community
  • 1
  • 1
De Novo
  • 7,120
  • 1
  • 23
  • 39
1

If you're really set on using a list, e.g., if this is for homework...

recognize that you're using a list of lists. So when you're trying to compare the ith list L[i] to the value of suburb, you're comparing your inner list, e.g., [4000, 'Charlestown'] to 'Charlestown'

Instead, you're going to want to compare L[i][1] to suburb.

Additionally, the function is not going to give you what you want (though you will avoid the error message) given the data you supplied, even when you fix that. Binary search is great, but it requires data be sorted according to the value you're searching for.

Here's a suggestion for that:

sorted(L, key=lambda L_inner: L_inner[1])

see if you can figure out how to implement that yourself. Some documentation: https://docs.python.org/3/howto/sorting.html#sortinghowto

De Novo
  • 7,120
  • 1
  • 23
  • 39
  • This makes sense to me however I'm not sure how I would implement it into my code. Would I need a for loop? – Henry Jones May 02 '17 at 09:53
  • Well, for one, do you see where in your code you're comparing a list to a string? Looks like @MrLeeh did the work for you... – De Novo May 02 '17 at 09:58
  • for two, you'll need to make sure your list is sorted according to the second element of the inner list. The short version you gave as an example is NOT sorted in that manner. I'll update the answer to illustrate. – De Novo May 02 '17 at 10:02
  • I believe I have sorted the list according to the second element. Would it help if I showed all of my code? – Henry Jones May 02 '17 at 10:11
  • You haven't. It looks like it's sorted according to the first element. Otherwise Henrytown would be before Jamestown (instead of 4001 before 4002). – De Novo May 02 '17 at 10:12
  • The actual list I'm using is different, it's much larger. I just wrote that one down as an example. I have a function in my code which sorts the list. It's the same as the code you wrote above. – Henry Jones May 02 '17 at 10:17
  • Then you're good :) Just recognize that if you did it exactly like the code I wrote above, but then passed L into the function rather than some other name you bound to the return value of the sorted function, your list is not going to be sorted correctly. And give me an upvote on this answer so I can comment on other people's posts ! :) – De Novo May 02 '17 at 10:23
  • I have created the function and it works because it returns the index value of the suburb or a '-1' if the suburb is not found. All I need to do now is figure out how to print the postcode matching to the suburb. – Henry Jones May 02 '17 at 10:28
  • Do you see your return statement? It's `return mid`. You want: `return L[mid][0]` – De Novo May 02 '17 at 10:29
  • Geat! Glad to help! – De Novo May 02 '17 at 10:43
0

In this case you just need to modify your binary search function. The error is that you compare a list with a string (see Exception message). That is because of this line:

L[mid] > target

where L[mid] is a tuple and target is a String. Use L[mid][1] > target instead.

def binarySearch(L, target):
    low = 0
    high = len(L)-1
    while low <= high:
        mid = (low + high)//2
        if L[mid][1] == target:
            return mid
        elif L[mid][1] > target:
            high = mid-1
        else:
            low = mid+1

NOTE: This only works if your list is sorted by your townsname otherwise your search goes in the wrong direction

MrLeeh
  • 5,321
  • 6
  • 33
  • 51
  • This did help a lot, thank you. However I'm not sure if my code worked because the output just produces the value '1' when I search for a valid suburb. – Henry Jones May 02 '17 at 10:13
  • I just realised that it is returning the index where the suburb is located, so the program works. I just need to figure out how to print the postcode for that suburb. – Henry Jones May 02 '17 at 10:22
0

The issue is that you have a multidimensional array and you are trying to match it to the name of the suburb. You need to match the second element of each nested array instead.

   def binarySearch(L, target):
    low = 0
    high = len(L)-1
    while low <= high:
        mid = (low + high)/2
        if L[mid][1] == target:
            return L[mid][0]
        elif L[mid][1] > target:
            high = mid-1
        else:
            low = mid+1

Note that I'm also returning L[mid][0] which will give you the pincode instead of the element number.

Ishaan Rajiv
  • 1