두 가지 다른 방법으로 목록에서 검색하는 함수

Question

저는 파이썬에 대해 처음 접해 보입니다. 그래서, 어떤 메소드가리스트에서 요소를 찾기 위해 함수에서 사용하는 것이 더 나은지 궁금합니다.

첫째

def search_binary(xs,target): 
    count = 0 
    for i in xs: 
     if i == target: 
      return count 
      count = count +1 
     else: 
      count = count +1 
      continue 
    return -1 

둘째이 비록 파이썬 실제로 특정 아니다

def search_binary(xs, target): 
    lb = 0 
    ub = len(xs) 
    while True: 
     if lb == ub: 
      return -1 

     mid_index = (lb + ub) // 2 

     item_at_mid = xs[mid_index] 


     if item_at_mid == target: 
      return mid_index  
     if item_at_mid < target: 
      lb = mid_index + 1  
     else: 
      ub = mid_index 

Answer 1

번째, 제가 O로 동작 (N) 시간은 두 번째는 이진 검색이며 O (log (n)) 시간에 작동합니다.

Answer 2

목록이 정렬되지 않았거나 작을 경우 lin을 사용하면 처음처럼 귀 검색 그러나 그것은 다음과 같이 수행해야 의미가있다 :

# linear search O(n) 
xs.index(target) 

목록 정렬 및 대형 당신은 그러나 같은 bisect을 사용하여이 작업을 수행하는 더 나은 것, 두 번째와 같은 이진 검색을 사용하는 경우는 이 :

# binary search O(log n) 
from bisect import bisect_left 
def search_binary(xs, target): 
    i = bisect_left(xs, target) 
    if i != len(xs) and xs[i] == target: 
     return i 
    raise ValueError