[알고리즘 with Python] - 이진탐색

참고서적: 이것이 취업을 위한 코딩테스트다 with python - 나동빈

 

up down 게임처럼 탐색범위를 반으로 쪼개면서 탐색하는 알고리즘. 따라서 시간복잡도는 O(logN)이다.

배열 내부 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 

 

처리해야 할 데이터 개수나 값이 1000만이상처럼 무척 높으면  이진탐색과 같이 O(logN)의 속도를 내는 알고리즘을 떠올려야 문제를 풀 수 있는 경우가 많다.  

 

# 이진 탐색 구현
def binary_search(array, target, start, end):
    if start > end:
        return None # 아무런 값을 반환하지 않고 종료
    mid = (start + end) // 2

    # 찾은경우 중간점 인덱스 반환
    if array[mid] == target:
        return mid
    # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인하기
    elif array[mid] > target:
        return binary_search(array, target, start, mid - 1)
    else:
        return binary_search(array, target, mid +1, end)
    


# n(원소의 개수)과 target(찾고자 하는 문자열) 입력받기
n, target = list(map(int, input().split()))

# 전체 원소 입력받기
array = list(map(int, input().split()))

# 이진 탐색 수행 결과 출력하기
result = binary_search(array, target, 0, n-1)
if result == None:
    print("원소가 존재하지 않습니다")
else:
    print(result + 1)