728x90
반응형
이진 탐색
: 데이터가 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘이다. 반으로 쪼개가면서 탐색을 하는데 내부의 데이터가 반드시 정렬되어있어야 함.
배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 x와 비교한다. x가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로 비교하고, 크다면 배열의 우측을 대상으로 다시 탐색한다.
-> 해당 값을 찾을 때까지 중간 값을 임의로 선택하고 비교하는 과정을 반복함.
예시)
my_list = [1, 9, 3, 5, 7, 13, 11, 17, 15] 라는 배열이 있음.
반드시 정렬 과정이 필요!
1 3 5 7 9 11 13 15 17 중에서 5를 찾고자 한다면
1 3 5 7 9 11 13 15 17
처음값 1, 끝값 17 일때, 중간값은 9.
1 3 5 7 9 11 13 15 17
찾으려는 데이터 5가 9보다 작으므로 11부터 17까지의 데이터는 더이상 볼 필요가 없다.
1 3 5 7
끝 값을 9의 하나 앞인 7로하면 처음값은 1, 끝값은 7, 중간값은 3이다.
찾으려는 데이터 5가 3보다 크므로 1부터 3까지의 데이터는 볼 필요가 없다.
5 7
처음 값을 1의 하나 뒤인 5로 해주면 처음값은 5, 끝값은 7, 중간값은 5이다.
중간점에 위치한 데이터 5는 찾으려는 값과 동일하므로 탐색을 종료한다!
"중간값 = 찾으려는 데이터의 값"
파이썬으로 구현한 이진탐색 알고리즘
# 리스트 data, 찾는 값 target
def binary_search(data, target):
start = 0
end = len(data) - 1
while start <= end: # 탐색할 범위가 남아 있는 동안 반복
mid = (start + end) // 2
if target == data[mid]: # 발견!
return mid
elif target < data[mid]: # 찾는 값이 더 작으면 왼쪽으로 범위를 좁히기
end = mid - 1
else: #찾는 값이 더 크면 오른쪽으로 범위를 좁히기
start = mid + 1
return -1 # 찾지 못했을 때
my_list = [1, 9, 3, 5, 7, 13, 11, 17, 15]
my_list.sort() # 반드시 정렬해주는 과정이 필요함
print(binary_search(my_list, 5)) # 리스트 data = my_list, 찾는 값 target = 5728x90
반응형