220120

선형(linear) 탐색 알고리즘과 이진(binary) 탐색 알고리즘을 구현하였다.

선형 탐색 방법

def linear_search(element, some_list):
    # 코드를 작성하세요.
    itr = len(some_list)
    for i in range(0, itr):
        if some_list[i] == element:
            return i
    return None

이진 탐색 방법

def binary_search(element, some_list):
   start_index = 0
   end_index = len(some_list)-1
   while len(some_list) != 0:
    ## 정답출력 (중앙값 == element)
    mid_index = (start_index + end_index)//2
    if element > some_list[end_index] or element < some_list[start_index]:
        return None
    if element == some_list[mid_index]:
        print('correct')
        return (start_index + end_index)//2
    # 중앙값 변화
    elif element > some_list[mid_index]:
        print('up')
        start_index = mid_index + 1
    elif element < some_list[mid_index]:
        print('down')
        end_index = mid_index - 1
    elif start_index == end_index:
        return None

이진 탐색법은 리스트의 중앙값과 element를 비교하며 범위를 좁혀가는 탐색법이다.
일반적으로 some_list의 길이가 길수록 선형 탐색보다 이진 탐색이 더 빨랐다. 다만 이진탐색의 경우 list가 정렬되어있어야 한다는 조건이 붙는다.