[알고리즘] 이분 탐색

이분탐색이란 무엇일까?

• 정렬된 자료를 반으로 나누어 탐색하는 방법
• 시간 복잡도 : O(log N)

코드 분석

def binary_search(left, right, target):
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            right = mid - 1
        else:
            left = mid + 1
    return None

• 움직여야 하는 값, 즉, 이 값을 움직여야 겠다. 를 정렬
• 자료의 중간 값이 찾고자 하는 값인지를 검사
• 아니면 대소관계를 비교하여 left와 right를 이동
• 맞으면 함수를 끝낸다.

STEP 00 (기본)

STEP 01 (중간 값 > Target)

STEP 02 (중간 값 < Target)

STEP 03 (중간 값 == Target)

• 종료

 

백준 참고 문제

https://www.acmicpc.net/problemset?sort=ac_desc&algo=12 

문제 - 1 페이지

 

❤ 본 포스팅에서 지적과 좋아요는 감사하게 받겠습니다.