이진 탐색

☝ 이진 탐색이란 정렬된 배열 에서 원하는 값을 탐색하기 위해 탐색 영역을 절반씩 줄여가는 알고리즘이다.

🎫 개념

가장 첫번째로 배열의 중간 값을 기준으로 찾고자 하는 값 x와 비교한다.
만약 x가 중간 값보다 크면 중간 값을 기준으로 우측을 탐색하고,
x가 중간 값보다 작으면 좌측을 탐색한다.
새로 갱신 된 탐색 영역에서 같은 방법으로 새로운 중간 값과 비교해 x를 찾을 때까지 이를 반복한다.

❓ 예시

예를 들어 [15, 17, 22, 29, 35, 47, 84] 이라는 배열 arr이 있다고 하자.
찾고자 하는 값 x는 35이다.

✔ step1
tmp(중간 값) = 29, x = 35
tmp < 35 이므로 tmp의 우측 탐색

✔ step2
arr = [35, 47, 84]
tmp = 47, x = 35
x < tmp 이므로 tmp의 좌측 탐색

✔ step3
arr = [35]
배열에 하나 남은 값과 x가 일치하므로 성공

🤔 x를 찾지 못하는 경우도 있을까?

배열의 길이가 0이 될 때까지 x를 찾지 못하면 실패하고 종료된다.

💻 이진 탐색 코드 구현 (python)

def binary_search(arr, x):
    l, r, = 0, len(arr)-1
    #l이 r보다 작거나 같을 동안
    while l <= r:
        m = (r + l) // 2
        #중간값이 타겟값과 같을 경우 위치 리턴
        if arr[m] == x:
            return m
        #중간값보다 타겟값이 작을 경우 중간값의 왼쪽 영역 탐색
        elif x < arr[m]:
            r = m - 1
        #중간값보다 타겟값이 크거나 같을 경우 중간값의 오른쪽 영역 탐색
        else:
            l = m + 1
    return -1

if __name__ == '__main__' :
    arr = list(map(int, input().split()))
    x = int(input())
    print(binary_search(arr, x))

⏰ 시간 복잡도 및 Big O 표기

예를 들어
[12, 23, 34, 45, 56, 67, 78, 89]인 배열에서 12를 찾으려면
배열의 길이가 N일 때
원소의 개수가 8개 -> 4개 -> 2개 ->1개 로 줄어들며 탐색이 3번 진행된 것을 알 수 있다.
따라서 시간 복잡도를 k라 하고, 배열의 길이를 N이라 하면
2^K = N 이다.
K = log2N
-> logN
따라서 이진 탐색의 시간 복잡도는 O(logN)이다.