[이진탐색] 정렬된 배열에서 특정 수의 개수 구하기 (Python)

📌이것이 취업을 위한 코딩테스트다 - CH15.이진탐색

✏️ 이진탐색

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

• 배열 내부의 데이터가 정렬되어 있을 때만 사용 가능.

• 세 가지 변수 필요 => 시작점, 끝점, 중간점.

• 시작점과 끝점은 탐색 범위 지정, 중간점은 찾고자하는 데이터와 비교.

  ---

👊 Q27. 정렬된 배열에서 특정 수의 개수 구하기

1.문제

N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있다. 이때 이 수열에서 x가 등장하는 횟수를 계산하고, x가 등장하지 않는 경우에는 -1을 출력.

---

2.체크포인트

시간복잡도 O(logN)으로 동작하는 알고리즘을 요구.
일반적인 선형탐색으로 풀 경우 시간 초과.
모든 원소가 정렬되어 주어짐 -> 이진 탐색 이용.

---

3.해결 방법

1. 원소가 등장하는 첫 번째 위치 파악하기. -> 이진 탐색
2. 원소가 등장하는 마지막 위치 파악하기. -> 이진 탐색
3. (마지막 위치 - 첫 번째 위치) + 1 은 원소의 등장 횟수

---

4.전체 코드

# 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               # target== mid, mid 가 첫 번째 위치일 때
            else:
                end = mid - 1  # target == mid 지만, 첫 번째 위치가 아닐 때, 범위의 마지막을 mid-1로 줄이고 다시 탐색
        elif array[mid] >= target:   # target 이 mid 보다 왼쪽에 있을 때, mid 의 왼쪽 범위 다시 탐색
            end = mid - 1
        else:
            start = mid + 1   # target 이 mid 의 오른쪽에 있을 때, mid 의 오른쪽 범위 다시 탐색
    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())       # 원소 수와, 찾는 값(x)를 공백으로 분리하여 입력 받음
array = list(map(int, input().split()))  #원소 배열 입력 받기

if binary_search_start(array, x, 0, len(array)-1) == -1 :   # 찾는 값이 배열에 없으면 -1 출력
        print(-1)
else:   # 찾는 값이 있으면 마지막 인덱스 - 첫번째 인덱스 + 1
    print(binary_search_end(array, x, 0, len(array)-1) - binary_search_start(array, x, 0, len(array)-1) + 1)

---

5.참고 사항

👉 bisect : 파이썬의 이진 탐색 라이브러리를 사용해서 풀이 가능.

from bisect import bisect_left, bisect_right

# 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
def count_by_range(array, left_value, right_value):
    right_index = bisect_right(array, right_value)
    left_index = bisect_left(array, left_value)
    return right_index - left_index

n, x = map(int, input().split()) # 데이터의 개수 N, 찾고자 하는 값 x 입력 받기
array = list(map(int, input().split())) # 전체 데이터 입력 받기

# 값이 [x, x] 범위에 있는 데이터의 개수 계산
count = count_by_range(array, x, x)

# 값이 x인 원소가 존재하지 않는다면
if count == 0:
    print(-1)
# 값이 x인 원소가 존재한다면
else:
    print(count)