[Binary Search] 이코테 “범위를 반씩 좁혀가는 탐색” Python 풀이

문제

• 이미 정렬된 데이터 중에서 특정 원소가 몇 번째 위치에 존재하는지 출력하시오.

입력 예시

10 7
1 3 5 7 9 11 13 15 17 19

10 7
1 3 5 6 9 11 13 15 17 19

출력 예시

4

원소가 존재하지 않습니다.

풀이

• 탐색 시작 위치와 탐색 종료 위치를 반복적으로 좁혀가며, 중간값과 탐색값을 비교하면 됩니다.
• 또한, start 가 end 보다 커졌을때를 탐색 불가능으로 판단하면 됩니다.

예제 코드

# n(원소의 개수)과 search(찾고자 하는 값)를 입력 받기
n, search = map(int,input().split())
# 전체 원소 입력 받기
n_list = list(map(int,input().split()))

def binary_search(start, end):
    # 못 찾았을 경우
    if (start > end):
        return None

    # 중간 index 찾기
    mid = (start+end)//2

    # 중간 index 의 값이 찾으려는 값과 같은지 확인
    if (n_list[mid] == search):
        return mid+1
    # 중간 index 의 값이 찾으려는 값보다 큰 경우
    elif (n_list[mid] > search):
        return binary_search(start, mid - 1)
    # 중간 index 의 값이 찾으려는 값보다 작은 경우
    else:
        return binary_search(mid+1, end)

# 탐색 시작 idx 정의
start = 0
end = len(n_list)-1

# 이진 탐색 수행 결과 출력
result = binary_search(start, end)
if (result == None):
    print("원소가 존재하지 않습니다.")
else:
    print(result)

참고

• 이것이 취업을 위한 코딩 테스트다. with python