二進制搜索的名稱

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

由於阿什維尼在他的評論所說，你可以使用字典中的蟒蛇。它會是這個樣子：

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

對方的回答是正確的，你應該使用字典，但由於即時猜測這是一個賦值第一你需要的是一個清單

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兼容的數據並返回選定項的函數。

爲了在易消化的步驟中解決您的更復雜的問題，背對自己。

注意：這顯然是一個學習如何實現算法的任務。如果真的要從文件中找到信息，那麼使用字典就會是錯誤的。正確的做法是閱讀每行，直到找到該文件的平均一半條目的比較結果爲止。沒有浪費的存儲空間，沒有浪費時間比較或哈希。