선형탐색(LinearSearch) & 이진탐색(BinarySearch)

선형탐색(LinearSearch) 

리스트의 처음부터 끝까지 순서대로 하나씩 탐색을 진행하는 알고리즘

 

 

def linear_search(element, some_list):
    # 여기에 코드를 작성하세요
    for e in some_list:
        if e == element:
            return some_list.index(e)
    return None

print(linear_search(2, [2, 3, 5, 7, 11]))
print(linear_search(0, [2, 3, 5, 7, 11]))
print(linear_search(5, [2, 3, 5, 7, 11]))
print(linear_search(3, [2, 3, 5, 7, 11]))
print(linear_search(11, [2, 3, 5, 7, 11]))

 

이진탐색(BinarySearch) 

이진 탐색 알고리즘은 선형 탐색 알고리즘과 달리, 정렬된 리스트를 전제로 합니다.

정렬된 리스트가 아니면 이 알고리즘은 적용이 불가능

1회 비교를 거칠 때마다 탐색 범위가 (대략) 절반으로 줄어들기 때문입니다.

 

def binary_search(element, some_list):
    # 여기에 코드를 작성하세요
    start_index = 0 
    end_index = len(some_list) - 1
    
    while start_index <= end_index: 
        mid_index = (start_index + end_index) // 2 
        if some_list[mid_index] == element:
            return mid_index 
        # mid element보다 element가 작을경우에는 end_index를 변경
        elif some_list[mid_index] > element: 
            end_index = mid_index - 1 
        # mid element보다 element가 클 경우에는 start_index 변경  
        else:  
            start_index = mid_index + 1 
    return None
        
            
            

print(binary_search(2, [2, 3, 5, 7, 11]))
print(binary_search(0, [2, 3, 5, 7, 11]))
print(binary_search(5, [2, 3, 5, 7, 11]))
print(binary_search(3, [2, 3, 5, 7, 11]))
print(binary_search(11, [2, 3, 5, 7, 11]))