좌충우돌 IT이야기

[설명]

이진 탐색은 찾고자하는 값을 중앙값을 기준으로 찾는 알고리즘입니다. 해당 알고리즘을 사용하려면 중요한 선행작업 필요합니다.

바로 순차정렬입니다. 찾고자하는 값이 x가 중앙값 보다 작다면 왼쪽을 탐색, 크다면 오른쪽을 탐색하기 때문입니다. 그러므로 이때 정렬이 되어 있지 않다면 우리가 원하는 값이 아닌 다른 값이 나오게 될것입니다.

만약 x = 3 이라면, 먼저 정렬된 배열의 중앙값을 찾습니다. 그 후 찾고자 하는 값은 2이므로 왼쪽을 탐색합니다.

2를 찾아왔지만, 원하는 값은 2보다 크므로 오른쪽을 탐색합니다.

[파이썬 코드]

a = [7, 8, 9, 1, 2, 3, 4, 5, 6]
a.sort(reverse=False)
low = 0
high = len(a)-1
while low <= high:
    p = (high + low) // 2
    if a[p] == k:
        print(p+1)
        break
    elif a[p] < k:
        low = p + 1
    else:
        high = p - 1