[알고리즘] 이진 탐색

개념

• 어떤 값을 찾을 때 정렬의 특징을 이용해 빨리 찾음
• 정렬되어 있을 경우, 어떤 값을 찾을 때 : O(N) -> O(lgN)
• 처음부터 생각하기 어려움, 쉬운 방법부터 생각하자

 

용례 및 특징

• 정렬된 숫자 중 특정 숫자를 찾아야 할 때
• 모두 탐색: O(N)
• 이진 탐색: O(lgN)

 

# 생각하기 어려우니 미리 외워두자
def search(st, en, target):
    # 종료 조건
    if st == en:
    // ~~
    return
    
    mid = (st + en) // 2
    if nums[mid] < target:
        search(mid + 1, en, target)
    else:
        (st, mid, target)

 

• Idea
  • 재귀함수 또는 while
  • 종료 조건 - 예외 케이스 준비
• 시간복잡도
  • O(lgN)
• 자료구조
  • 사용 안 함