이진 탐색
찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 방법

✅ 문제

N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 x가 등장하는 횟수를 계산하세요.
단, 이 문제의 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 '시간 초과' 판정을 받습니다.

입력 예시

7 2
1 1 2 2 2 2 3

출력 예시

4

💻 코드

N, x = map(int, input().split())
data = list(map(int, input().split()))

start = 0
end = len(data) - 1
total = 0
while start <= end:
    mid = (start + end) // 2
    if x == data[mid]:
        for i in range(mid, -1, -1):
            if data[i] == x:
                total += 1
            else:
                break
        for j in range(mid + 1, len(data)):
            if data[j] == x:
                total += 1
            else:
                break
        break    
    elif x >= data[mid]:
        start = mid + 1
    else:
        end = mid - 1

if total == 0:
    print(-1)
else:
    print(total)

설계

이진 탐색으로 x가 있는지 확인하고, x가 있다면 x의 위치에서 앞으로 x의 개수와 뒤로 x의 개수를 센다.
이 문제 풀이는 x의 개수가 많지 않다면 시간 복잡도 O(logN)으로 풀리지만 N개의 원소를 가지고 있는 수열이 x로만 이루어져 있다면 시간 복잡도가 O(N)일 것이다.
따라서 완벽한 풀이는 아니다..

➕ 다른 풀이 1

이진 탐색으로 첫 번째, 마지막 위치 구하기

# x의 첫 번째 위치 구하기
def binary_search_start(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        if array[mid] == target:
            if mid - 1 < 0 or array[mid - 1] != target:
                return mid
            else:
                end = mid - 1 
        elif array[mid] >= target:
            end = mid - 1
        else:
            start = mid + 1
    return -1

# x의 마지막 위치 구하기
def binary_search_end(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        if array[mid] == target:
            if mid + 1 >= len(array) or array[mid + 1] != target:
                return mid
            else:
                start = mid + 1 
        elif array[mid] >= target:
            end = mid - 1
        else:
            start = mid + 1
    return -1

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

if binary_search_start(array, x, 0, len(array)-1) == -1 :
        print(-1)
else:
    print(binary_search_end(array, x, 0, len(array)-1) - binary_search_start(array, x, 0, len(array)-1) + 1)

이진 탐색으로 x의 첫 번째 위치와 마지막 위치를 구한다. 첫 번째 위치를 구할 때에는 target인 x 앞의 원소가 x와 같지 않은지 확인하거나 수열의 인덱스를 넘어 가지 않는지 확인하여 첫 번째 위치를 구하고, 마지막 위치를 구할 때에는 target인 x 뒤의 원소가 x와 같지 않거나 수열의 인덱스를 넘어 가지 않는지 확인하여 구한다.

➕ 다른 풀이 2

bisect 라이브러리 사용

from bisect import bisect_left, bisect_right

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

count = bisect_right(array, x) - bisect_left(array, x)
if count == 0:
    print(-1)
else:
    print(count)

📝 정리

🔖 (파이썬) bisect 이진 탐색을 쉽게 구현하는 라이브러리

• bisect_left(a, x) : 정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽입할 가장 왼쪽 인덱스를 찾는 메서드
• bisect_right(a, x) : 정렬된 순서를 유지하도록 리스트 a에 데이터 x를 삽입할 가장 오른쪽 인덱스를 찾는 메서드
• 시간 복잡도 : O(logN)

from bisectimport bisect_left, bisect_right