선형(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가 정렬되어있어야 한다는 조건이 붙는다.