인덱싱 오류가 파이썬이 이진 검색 방법을 실행할 때

Question

def unique(ip): 
     file = open("/home/USER/Desktop/ipAddreses.txt",'r') 
     list = file.readlines() 
     list.sort() 
     low = 1 
     hi = len(list) 
     target = convertToStr(ip) 
     if hi > 1: 
       while low <= hi: 
       mid = low + (hi-low)/2 
       if list[mid] == target: 
        file.close() 
        return False    
       elif list[mid] < target: 
        low = mid+1 
       else: 
        hi = mid-1 
     else: 
       if target == list[0]: 
        return False 

file.close() 
return True 

이 오류가 :

if list[mid] == target: 
    IndexError: list index out of range 

목적은 모든 무작위로 생성 된 IP 주소가 고유 확인하기 위해 생성 된 IP 주소를 통해 검색하는 것입니다. 전에 일하고 있었어 ... 집에 돌아 왔는데 이제이 오류가 발생합니다

Answer 1

나는 즉시 코드를 사용하여 문제를 해결하는 방법을 볼 수는 없지만, 그냥 손에서 문제를 해결하려는 경우, 이것은 아마 그것을 할 수있는 가장 좋은 방법은 아니다.

• 이진 검색을 정렬하면 일반적으로 배열에 대해 직선적 인 선형 검색을 수행하는 것보다 거의 항상 나쁜 것입니다. 정렬은 O (n log n)이며 실제로는 배열의 각 요소를 적어도 한 번 ""보고해야하며 전체 파일의 복사본을 적어도 하나 이상 메모리에 저장해야합니다. 파일을 반복하는 경우 각 요소를 최대 한 번만보고 일정한 양의 메모리 만 사용합니다.

• 어쨌든 (연습을하지 않는 한) 바이너리 검색을 구현해서는 안됩니다. 대신 the bisect module을 사용하십시오.

• file (target == list[0] 부분)을 명시 적으로 닫지 않은 코드의 이탈 경로가있는 것처럼 보입니다. 이것이 with 문장이 좋은 이유입니다; 그들은 당신을 위해 그것을 처리합니다.

이 대신처럼 할 수있는 :

def unique(ip): 
    ip_str = convertToStr(ip) 
    with open("/home/USER/Desktop/ipAddreses.txt", 'r') as f: 
     return all(line.rstrip() != ip_str for line in f) 

는 IP 주소의 무리에 unique를 호출려고하는 경우에, 당신은 전체 파일마다 읽기 않도록, 그리고 더 얻을 수 빠른 조회, 사용 set :에 비교 말했다

with open("/home/USER/Desktop/ipAddreses.txt", 'r') as f: 
    ip_addresses = set(line.rstrip() for line in f) 

def unique(ip): 
    return convertToStr(ip) not in ip_addresses 

---

, 차이점은 while low <= hi을 사용하지만 그들은 while lo < hi을 사용하고 hi = mid - 1은 hi = mid을 사용하는 것입니다. 나는 당신이 검색 할 문자열이 목록에서 가장 큰 문자열 일 경우 low == hi == len(list)으로 끝나기 때문에 mid = len(list)을 설정하면 list[mid] 일 때마다 깨진다는 것을 확신한다. .

Answer 2

목록에 mid가 있는지 확인하십시오.

if mid in list: 
    if list[mid] == target: 
     # ...