파이썬(알고리즘) :: 오름차순으로 정렬 후 위치 찾기 (이분 검색)

이번에는 알고리즘 유형 중 이분 검색에 대해 정리하려고 한다.

 

문제 유형으로는 숫자로 이루어진 문자열을 Input으로 받은 후 오름차순으로 정렬하여 특정 숫자의 인덱스 값을 반환하는 문제이다.

 

# 풀이 과정

먼저 입력받은 문자열을 sort 메서드로 오름차순으로 정렬한다. 

 

그 다음 아래 그림과 같이 첫 인덱스를 Left 그리고 마지막 인덱스에 Right를 설정한다.

그리고 Left와 Right의 평균 값을 Middle로 설정한다.

그 후 Middle 값이 찾고자 하는 숫자와 같은지 비교 후 같으면 Middle 값의 인덱스를 리턴하고, 그게 아니라면 Middle과 크기 비교 후 Middle이 크면 Left = Middle + 1 로 설정하고 그게 아니라면 Right = Middle -1 로 설정한다.

 

그리고 계속 똑같이 반복하여 원하는 숫자를 검색한다.

 

해당 방법의 모든 리스트의 요소를 검색하기 위해서는 리스트의 길이 만큼 검색해야하지만 이분 검색은 계속 절반씩 자르기 때문에 아무리 많이 검색해봤자 리스트이 길이 보다 적게 검색한다는 장점이 있다.

 

# 코드

def search(input_list, m):
    input_list = list(map(int, input_list.split()))
    input_list.sort()
    
    left = 0
    right = len(input_list)

    print(input_list)

    while left <= right:
        middle = (left + right)//2
        if input_list[middle] == m:
            return middle+1
        elif input_list[middle] > m:
            right = middle - 1
        else:
            left = middle + 1


input_list = "23 27 35 62 47 92 99 31"
m = 35

print(search(input_list, m))

 

# 실행 결과 

[23, 27, 31, 35, 47, 62, 92, 99]
4