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

p. 367

 

방법1. 특정 수의 개수 다 세기

cnt=0
def b_s(array, target, start, end):
  global cnt
  if start>end:
    return cnt
  middle=(start+end)//2
  if array[middle]==target:
    cnt+=1
    b_s(array, target, middle+1, end)
    b_s(array, target, start, middle-1)
  elif array[middle] < target:
    b_s(array, target, middle+1, end)
  else:
    b_s(array, target, start, middle-1)
  

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

b_s(array, x, 0, len(array)-1)
if cnt==0:
  print("-1")
else:
  print(cnt)

 

방법 2. 연속된 특정수의 위치 구해서 빼기(bisect)

from bisect import bisect_right, bisect_left

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

left=bisect_left(array,x)
right=bisect_right(array,x)

if left==right:
  print("-1")
else:
  print(right-left)

 

방법 3. bisect 구현하여 방법 2처럼 짜기

def first(array, target, start, end):
  if start>end:
    return None
  mid=(start+end)//2

  #해당 값을 가지고 있는 원소 중에서 가장 왼쪽에 있는 경우에만 인덱스 반환
  if (mid==0 or target>array[mid-1]) and array[mid]==target:
    return mid
  elif array[mid]>=target:
    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

  if (mid==n-1 or target<array[mid+1]) and array[mid]==target:
    return mid
  elif array[mid]>target:
    return last(array, target, start, mid-1)
  else:
    return last(array, target, mid+1, end)


def count_by_value(array,x):
  n=len(array)

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

  # 수열에 x가 존재하지 않는 경우
  if a==None:
    return 0
  
  # x가 마지막으로 등장한 인덱스 계산
  b=last(array, x, 0, n-1)

  return b-a+1

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

# 값이 x인 데이터의 개수 계산
count=count_by_value(array, x)

if count ==0:
  print("-1")
else:
  print(count)