Binary search through nested list in python
Question: I have a homework question asking:

> Write a function called readCountries that reads a file and returns a list
> of countries. The countries should be read from this file (countries.txt),
> which contains an incomplete list of countries with their area and
> population. Each line in this file represents one country in the following
> format:
>  
>  
>     name, area(in km2), population
>  
>
> When opening the file your function should handle any exceptions that may
> occur. Your function should completely read in the file, and separate the
> data into a 2-dimensional list. You may need to split and strip the data as
> appropriate. Numbers should be converted to their correct types. Your
> function should return this list so that you can use it in the remaining
> questions.

I have a text file called "countries.txt" with a list of a bunch of countries,
their area, and their population.

Sample of "countries.txt":

    
    
    Afghanistan,    647500.0,   25500100
    Albania,    28748.0,    2821977
    Algeria,    2381740.0,  38700000
    

This is the code I have and it works:

    
    
    def readCountries(filename):
        '''read a file and print it to the screen'''
        countryList = []
        for line in open(filename):
            with open(filename) as aFile:
                countries = aFile.read()
                countryList.append(line.strip().split())
        aFile.close()
    
        return countryList 
    

Sample of output when I ran the question:

    
    
    >>> countryList = readCountries("countries.txt")
    >>> countryList
    [['Afghanistan,', '647500.0,', '25500100'], ['Albania,', '28748.0,', '2821977'], ['Algeria,', '2381740.0,', '38700000']
    

The next question asks:

> Write a function called printCountry that takes a string representing a
> country name as a parameter. First call your answer from question 1 to get
> the list of countries, then do a binary search through the list and print
> the country's information if found. And should print out:
>  
>  
>     printCountry("Canada")
>       Canada, Area: 9976140.0,    Population: 35295770
>     printCountry("Winterfell")
>       I'm sorry, could not find Winterfell in the country list.
>  

But I can't figure it out.

When I tried to do the coding for this question, I typed:

    
    
    countryList = readCountries("countries.txt")  
    def printCountry(name):
        lo, hi = 0, len(countryList) - 1
        while lo <= hi:
            mid = lo + (hi - lo) // 2
            country = countryList[mid]
            test_name = country[0]
            if name > test_name:
                lo = mid + 1
            elif name < test_name:
                hi = mid - 1
            else:
                return country[0] + ", Area: " + str(country[1]) + ",    Population: " + str(country[2])
        return "I'm sorry can not find " + str(name)
    

and the result was:

    
    
    >>> printCountry("Canada")
    'Sorry can not find Canada'
    

even though Canada is in the text. Where did I go wrong?


Answer: Your binary search code is (mostly) ok, but there are a couple of problems in
your code that reads in the list of countries.

Your file opening & reading code is strange. It's like you've combined two
different approaches to reading data, so you are opening the file multiple
times.

Fortunately, the effects of these lines:

    
    
    with open(filename) as aFile:
        countries = aFile.read()
    

don't affect the output of the `readCountries` function because you don't do
anything else with `countries`.

Also, in the description of your assignment it says to "strip the data as
appropriate. Numbers should be converted to their correct types", which your
code doesn't do. And as my hint above implied, that means the country names in
your list still had the commas attached to them, so the binary search couldn't
find them (unless you included the comma in the search name).

Anyway, here's a cleaned up version that's designed to run on Python 2.6 or
later.

    
    
    from __future__ import print_function
    
    def readCountries(filename):
        countryList = []
        with open(filename) as aFile:
            for line in aFile:
                line = line.strip().split()
                #Remove anny trailing commas from each field
                line = [s.rstrip(',') for s in line]
                #Convert area to float and population to int
                line = [line[0], float(line[1]), int(line[2])]
                #print line
                countryList.append(line)
        return countryList
    
    countryList = readCountries("countries.txt")
    
    def printCountry(name):
        lo, hi = 0, len(countryList) - 1
        while lo <= hi:
            mid = lo + (hi - lo) // 2
            country = countryList[mid]
            test_name = country[0]
            if name > test_name:
                lo = mid + 1
            elif name < test_name:
                hi = mid - 1
            else:
                print('  {0}, Area: {1}, Population: {2}'.format(*country))
                break
        else:
            print("  I'm sorry, could not find {0} in the country list.".format(name))
    
    #tests
    printCountry("Canada")
    printCountry("Winterfell")
    
    print('- ' * 20)
    
    #make sure we can find the first & last countries.
    printCountry("Afghanistan")
    printCountry("Nowhere")
    

Here's the data file I ran it on:

**countries.txt**

    
    
    Afghanistan,    647500.0,   25500100
    Albania,    28748.0,    2821977
    Algeria,    2381740.0,  38700000
    Canada,     9976140.0,  35295770
    Nowhere,    1000.0      2345678
    

And this is the output it produced:

    
    
      Canada, Area: 9976140.0, Population: 35295770
      I'm sorry, could not find Winterfell in the country list.
    - - - - - - - - - - - - - - - - - - - - 
      Afghanistan, Area: 647500.0, Population: 25500100
      Nowhere, Area: 1000.0, Population: 2345678
    

