Двоичный поиск имени

Question

У меня есть список стран в отдельном файле (countries.txt), и мне нужно сделать двоичный поиск, чтобы найти страну, и для этого указать информацию, предоставленную на ней.

Мой файл:

Afghanistan, 647500.0, 25500100 

Albania, 28748.0, 2821977 

Algeria, 2381740.0, 38700000 

American Samoa, 199.0, 55519 

Andorra, 468.0, 76246 

Angola, 1246700.0, 20609294 

Если бы я хотел, чтобы найти площадь и население для Албании, и я поставил getCountry(Albania) в раковине, как бы я это утверждать предоставленную информацию?

меня это до сих пор ...

def getCountry(key): 

    start = "%s" #index 
    end = len("%s")-1 #index 
    while start<=end: 
     mid = (start + end)/2 
     if '%s'[mid] == key: #found it! 
      return True 
     elif "%s"[mid] > key: 
      end = mid -1 
     else: 
      start = mid + 1 
    #end < start 
    return False 

Answer 1

Как Ashwini предложил в своем комментарии, вы можете использовать словарь в Python. Это будет выглядеть примерно так:

countries = {'Afghanistan': (647500.0, 25500100), 

    'Albania': (28748.0, 2821977), 

    'Algeria': (2381740.0, 38700000), 

    'American Samoa': (199.0, 55519), 

    'Andorra': (468.0, 76246), 

    'Angola': (1246700.0, 20609294)} 

print countries['Angola'][0] 

Вы можете узнать больше о dictionary и tuple от this python documentation

Answer 2

другой ответ правильный вы должны использовать словарь, но так как Im предполагаю, что это назначение первым что вам нужно, это список

with open("countries.txt") as f: 
    #filter(none,a_list) will remove all falsey values (empty strings/lists/etc) 
    #map(some_function,a_list) will apply a function to all elements in a list and return the results as a new list 
    #in this case the iterable we are handing in as a_list is an open file handle and we are spliting each line on "," 
    country_list = filter(None,map(lambda x:x.split(","),f)) 

тогда вам просто нужно искать через упорядоченный список, как и любой другой двоичный поиск

для того, чтобы сделать бинарный поиск вы сделать что-то вроде (рекурсивную версию)

def bin_search(a_sorted_list,target): 
    mid_pt = len(a_sorted_list) // 2 
    if target < a_sorted_list[mid_pt]: 
     return bin_search(a_sorted_list[:mid_pt], target) 
    elif target > a_sorted_list[mid_pt]: 
     return bin_search(a_sorted_list[mid_pt:], target) 
    elif target == a_sorted_list[mid_pt]: 
     return mid_pt 

в вашем случае вам потребуются некоторые незначительные изменения

Answer 3

Я хотел бы использовать словарь:

def get_countries(filename): 
    with open(filename) as f: 
     country_iter = (line.strip().split(',') for line in f) 
     return { 
      country: {"area": area, "population": population} 
      for country, area, population in country_iter 
     } 

if __name__ == '__main__': 
    d = get_countries("countries.csv") 
    print(d) 

Если у вас действительно есть ваше сердце, установленное на двоичном поиске, это выглядит примерно так:

def get_countries(filename): 
    with open(filename) as f: 
     return [line.strip().split(',') for line in f] 

def get_country_by_name(countries, name): 
    lo, hi = 0, len(countries) - 1 
    while lo <= hi: 
     mid = lo + (hi - lo) // 2 
     country = countries[mid] 
     test_name = country[0] 
     if name > test_name: 
      lo = mid + 1 
     elif name < test_name: 
      hi = mid - 1 
     else: 
      return country 
    return countries[lo] if countries[lo][0] == name else None 

if __name__ == '__main__': 
    a = get_countries("countries.csv") 
    print(a) 
    c = get_country_by_name(a, "Albania") 
    print(c) 

Но это кодирование двоичного поиска с верхней части головы. Если вы не должны кодировать бинарный поиск и может использовать подпрограмму библиотеки вместо этого, он выглядит следующим образом:

from bisect import bisect_left 

def get_country_by_name(countries, name): 
    country_names = [country[0] for country in countries] 
    i = bisect_left(country_names, name) 
    return countries[i] 

Answer 4

властвуй эту проблему поэтапно.

1. Начните с сортированного списка и реализуйте двоичный поиск в списке в функции.
2. Удостоверьтесь, что он работает для пустых списков, списков одного элемента и т. Д.
3. Напишите функцию, чтобы взять несортированный список, отсортировать его и вернуть результат на нем из первой функции.
4. Напишите функцию, которая берет список кортежей со строкой в ​​качестве ключа и других строк в качестве данных. Он должен сортировать данные на вашем ключе и возвращать то, что вы хотите.
5. Напишите функцию, которая считывает файл и создает данные, совместимые с 4, и возвращает выбранный элемент.

Окунитесь на спину для решения вашей более сложной проблемы в удобоваримых шагах.

Примечание: Это явно задание, чтобы узнать, как реализовать алгоритм. Если бы было действительно найти информацию из файла, использование словаря было бы просто ошибкой. Правильно было бы читать каждую строку до тех пор, пока страна не была найдена, чтобы сделать одно сравнение в среднем по половине записей в файле. Никакое нерациональное хранение, не потраченное время в сравнении или хеширование.