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

문제

이코테 367p

접근

매우 긴 탐색 대상이 정렬이 되어있다? -> 이진 탐색

1차 Try

def binary_search(arr, target) :
  start, end = 0, len(arr)-1
  while (start <= end) : 
    mid = (start+end)//2 
    if arr[mid] < target : # 타겟보다 작다 -> 더 큰 숫자 탐색
      start = mid + 1
    elif arr[mid] > target : # 타겟보다 크다 -> 더 작은 숫자 탐색
      end = mid -1
    else : #정답발견
      return target  
  return -1 # x인 원소가 하나도 없음


## arr에서 x와 x의 index가 주어지면, x와 같은값의 원소 갯수를 좌우로 탐색하여 리턴
def how_many_x(arr, idx, x) : 
  start, end = idx, idx
  while True : 
    if arr[start] != x : break
    else : start -= 1
    if arr[end] != x : break
    else : end += 1
  return end-start+1
  
N, x = map(int, input().split())
arr = list(map(int, input().split()))

first_seen_idx = binary_search(arr, x)
print(first_seen_idx)
if first_seen_idx == -1 : print(-1)
else : print(how_many_x(arr, first_seen_idx, x))

1. 이진탐색으로 X의 위치를 찾는다 (binary_search)
2. 찾은 X위치를 바탕으로 앞뒤로 한칸씩 시작과 끝을 찾아나간다(how_many_x)

그런데 답지를 보니까, 더 좋은 접근이 있다ㅎㅎ
이렇게 풀면 how_many_x에서 X위치 시작과 끝을 찾는데 오래걸린다

Try 2

답지를 보고 개념을 이해한 다음 다시 구현해봤다.

# target을 찾는다
def binary_search(arr, target) :
  start, end = 0, len(arr)-1
  while (start <= end) : 
    mid = (start+end)//2 
    if arr[mid] < target : # 타겟보다 작다 -> 더 큰 숫자 탐색
      start = mid + 1
    elif arr[mid] > target : # 타겟보다 크다 -> 더 작은 숫자 탐색
      end = mid -1
    else : #정답발견
      return target  
  return -1 # x인 원소가 하나도 없음

# 가장 왼쪽에서 시작되는 인덱스를 찾는다
def left_binary_search(arr, target, target_idx) :
  left, right = 0, target_idx
  while (left <= right) : 
    mid = (left+right)//2
    if (mid == 0 or arr[mid-1] < arr[mid]) and arr[mid] == target  : # 정답 찾은 경우
      return mid
    elif arr[mid] < target : # 중간점이 타겟보다 작은경우 -> left를 늘려야
      left = mid + 1
    else : # 중간점 = 타겟값인 경우 -> right를 줄여야
      right = mid -1

# 가장 오른쪽에서 시작되는 인덱스를 찾는다
def right_binary_search(arr, target, target_idx) : 
  left, right = target_idx, len(arr)-1
  while (left <= right) : 
    mid = (left+right)//2
    if (mid == len(arr)-1 or arr[mid+1] > arr[mid]) and arr[mid] == target  : # 정답 찾은 경우
      return mid
    elif arr[mid] > target : # 중간점이 타겟보다 큰 경우 -> right를 줄여야
      right = mid -1
    else : # 중간점 = 타겟값인 경우 -> left를 늘려야
      left = mid +1
     
N, x = map(int, input().split())
arr = list(map(int, input().split()))

first_seen_idx = binary_search(arr, x)
if first_seen_idx == -1 : # 존재하지 않는 경우 : -1 리턴
  print(-1)
else : # 존재하는 경우 가장 처음 시작점과 끝점 구해서 전체 갯수 구하기
  start = left_binary_search(arr, x, first_seen_idx)
  end = right_binary_search(arr, x, first_seen_idx)
  print(end - start + 1)

가장 왼쪽에서 시작되는 인덱스와 가장 오른쪽에서 시작되는 인덱스도 이진탐색으로 풀어봤다 😊