Binary Searching

Question

I have this list called countries.txt that list all the countries by their name, area(in km2), population (eg. ["Afghanistan",647500.0,25500100]).

def readCountries(filename):
 result=[]
 lines=open(filename)
 for line in lines:
 result.append(line.strip('\n').split(',\t'))
 for sublist in result:
 sublist[1]=float(sublist[1])
 sublist[2]=int(sublist[2])

This takes in the list and prints it out. I want to creates a binary search and search through the list and print the country's information if found. With this code it should do this

printCountry("Canada") Canada, Area: 9976140.0, Population: 35295770

printCountry("Winterfell") I'm sorry, could not find Winterfell in the country list.

But it prints I'm sorry, could not find Canada in the country list 4 times then prints Canadas information.

What is going on?

def printCountry(country):
 myList=readCountries('countries.txt')
 start = 0
 end = len(myList)-1
 while start<=end:
 mid =(start + end) / 2
 if myList[mid][0] == country:
 return '%s, Area: %.3f, Population: %i' %(country,myList[mid][1],myList[mid][2])
 elif myList[mid][0] > country:
 end = mid - 1
 else:
 start = mid + 1
 print "I'm sorry, could not find %s in the country list" %(country)

• Caramiriel: I think the print should be outside the while loop.

Answer 1

The last line

print "I'm sorry, could not find %s in the country list" %(country)

should be outside the while loop. Also make sure the loop completed without finding the key in the file, then only you will be sure that the country name does not exist in the list.

# If condition taken from Michel's answer.
if start > end:
 print "I'm sorry, could not find %s in the country list" %(country)

Answer 2

You have to move your unsuccessful message after the while loop and check if start> end (that means that the country was not found):

myList = readCountries('countries.txt')
start = 0
end = len(myList) - 1
while start<=end:
 mid = (start + end) / 2
 if myList[mid][0] == country:
 return '%s, Area: %.3f, Population: %i' %(country,myList[mid][1],myList[mid][2])
 elif myList[mid][0] > country:
 end = mid - 1
 else:
 start = mid + 1
if start > end:
 print "I'm sorry, could not find %s in the country list" %(country)

• R Nar: you dont need the if statement since the function will return if it is found.