이진탐색

개념

탐색 범위를 반으로 줄여나가며 데이터를 빠르게 탐색하는 기법.

단, 배열 내부가 정렬되어있을 때에만 사용 가능하며 세가지 변수(시작점, 끝점, 중간점)가 사용된다.

과정

시작점, 끝점은 탐색하고자 하는 범위를 나타내기 위해 사용하고 탐색 범위의 중간점에 있는 데이터와 찾고자 하는 데이터를 비교합니다. 예를 들어서 이미 정렬이 된 0부터 9까지의 데이터 중에서 이진 탐색으로 2를 찾는 과정은 다음과 같은 과정으로 이뤄집니다.

 

# 과정1
0      1      2      3      4      5      6      7      8      9  
시작점                      중간점                               끝점

# 과정2
0      1      2      3      4      5      6      7      8      9  
시작점 중간점          끝점

# 과정3
0      1      2      3      4      5      6      7      8      9  
             시작점   끝점
             중간점

구현

"""
문제
N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어있다. 이때 수열에서 x가 등장하는 횟수 구하라.
단, 하나도 없을 시에는 -1 출력

input1
7 2
1 1 2 2 2 2 3

input2
7 4
1 1 2 2 2 2 3

"""

def count_by_value(n, x, array):
    # x가 처음 등장한 인덱스
    a = first(array, x, 0, n-1)

    # a값이 없는 경우, 0
    if a is None:
        return 0
    b = last(array, x, 0, n-1)

    return b - a + 1


def first(array, target, start, end):
    # 계속 이진탐색 진행하다보면 시작점 끝점 뒤집히게 됨
    if start > end:
        return None

    mid = (start + end) // 2

    # 중간점이 0이거나 가장 왼쪽에 있는 target 값인 경우에만 return
    if (mid == 0 or target > array[mid-1]) and array[mid] == target:
        return mid
    # 중간값보다 타겟값이 작거나 같으면 왼쪽으로 다시 찾음
    elif target <= array[mid]:
        return first(array, target, start, mid-1)
    # 중간값보다 타겟값이 크면 오른쪽으로 다시 찾음
    else:
        return first(array, target, mid + 1, end)


def last(array, target, start, end):
    # 계속 이진탐색 진행하다보면 시작점 끝점 뒤집히게 됨
    if start > end:
        return None

    mid = (start + end) // 2
    # 중간점이 0이거나 가장 오른쪽에 있는 target 값인 경우에만 return
    if (mid == n-1 or target < array[mid + 1]) and array[mid] == target:
        return mid
    # 중간값보다 타겟값이 작으면 왼쪽으로 다시 찾음
    elif target < array[mid]:
        return last(array, target, start, mid - 1)
    else:
        return last(array, target, mid + 1, end)


n, x = map(int, input().split())
array = list(map(int, input().split()))


count = count_by_value(n, x, array)


if not count:
    print(-1)
else:
    print(count)

 

파이썬 라이브러리를 이용한 구현

# 파이썬에는 표준 라이브러리에 bisect라는 이진탐색 모듈이 있으므로 쉽게도 사용 가능함

from bisect import bisect_left, bisect_right
n, x = map(int, input().split())
array = list(map(int, input().split()))
array.sort()

# 주의할 점: bisect는 x가 들어갈 위치를 반환함.
a = bisect_left(array, x)
b = bisect_right(array, x)

print(b-a)

 

정리

이진탐색은 처음에 n/2, 1/2 *n/2, 1/2**1/2 *n/2 ... 하게 실행되기 때문에 시간 복잡도는 O(log2N)이다.