[9일차] 05 탐색 : 05-3 이진 탐색

함께 푼 문제

[백준 / 이진 탐색] 10815 : 숫자 카드 (python)

 

이진 탐색

데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘.
대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다.

• 시간 복잡도 : O(logN)
• 데이터가 정렬돼 있어야 함

이진 탐색 과정

 

파이썬 구현

A = [4, 8, 10, 5, 2, 7, 6, 3, 9, 1]

A.sort() # **데이터 정렬**

start = 0
end = len(A) - 1

find = 2   # 찾을 값

while start <= end:
    mid = (start + end) // 2
    if A[mid] < find:
        start = mid + 1
    elif A[mid] > find:
        end = mid - 1
    else:
        print(A[mid]) # 2
        break # 값 찾으면 종료