코딩테스트 - 이진 탐색

이진 탐색은 탐색 알고리즘 중에 하나이다. 분명히 프로그래밍 수업할 때 배운 것 같은 기분이 든다... 데이터에서 탐색 범위를 줄여나가면서 원하는 데이터를 탐색하는 알고리즘이라고 한다. 이때 중요한 것은 찾고자 하는 데이터가 정렬되어 있어야 한다는 점이다. 즉, 정렬된 데이터에서 탐색 범위를 줄여 가면서 찾고자 하는 값을 찾는 알고리즘이다. 정렬된 데이터에서만 사용이 가능하다는 단점이 있지만, 탐색이 반복될 때마다 탐색 범위가 절반으로 줄기 때문에 탐색 속도가 빠르다는 장점이 있다.

data = [5, 10, 20, 25, 30, 35, 38, 50, 65, 70, 75, 80, 85, 90, 95]

left_index, right_index = 0, len(data) - 1

score = int(input('찾고자 하는 값을 입력하시오 '))

while left_index <= right_index:
    mid_index = (left_index + right_index) // 2

    if score < data[mid_index]:
        right_index = mid_index - 1
    elif score > data[mid_index]:
        left_index = mid_index + 1
    elif score == data[mid_index]:
        break

print(f"{score}는 {mid_index}번째 index입니다.")

출력

찾고자 하는 값을 입력하시오 80
80는 11번째 index입니다.

위에 사진은 작성한 코드를 설명하기 위해 만들었다. 이진 탐색은 탐색범위를 절반씩 줄여나가는데에 의미가 있다. 처음 탐색은 전체 범위에서 진행된다.
예를 들어 80을 찾는다고 가정하자. 전체 범위의 중간 값은 7이 된다. data에서 7의 index값을 갖는 숫자는 '50'이다. 50은 80보다 작으니 left를 변경한다. 중간값(mid)보다 1크게 만들고 탐색을 다시 시작한다. 8~14까지 index범위에서 가운데 값은 11이다. 11의 index를 갖는 값은 80이므로 탐색이 종료된다.