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

정렬이 되어있지 않다면 정렬을 해주고, 만약 정렬이 되어 있따면 이진탐색을 통해  O(log n) 탐색이 가능합니다.

이진 탐색을 통해 해당 수를 탐색하며 target 값과 일치할 때 해당 값이 그 값중에 최대한 왼쪽 인덱스인지 혹은 오른쪽 인덱스인지 확인하면 됩니다.

 

해당 수가 0 인덱스이거나 현재 값이 target과 동일한데 그 이전 값이 target보다 작은 경우 해당 값중 가장 왼쪽이라 할 수 있습니다.

 

혹은 오른쪽은 이의 반대로 탐색가능합니다.

 

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

 

nums = list(map(int, input().split()))

 

def find_first(nums,target):

    start = 0

    end = len(nums)-1

    

    while start<=end:

        mid = (start+end)//2

        if nums[mid]==target:

            if (mid ==0 or nums[mid-1]<target) and nums[mid]==target:

                return mid

        

        if nums[mid]>=target:

            end = mid -1

        else:

            start = mid +1

    return -1

 

def find_second(nums, target):

    start = 0

    end = len(nums)-1

    

    while start<=end:

        mid = (start+end)//2

        if nums[mid]==target:

            if (mid == len(nums)-1 or nums[mid+1]>nums[mid]) and nums[mid]==target:

                return mid

        if nums[mid]>=target:

            end = mid -1

        else:

            start = mid+1

 

a = find_first(nums, x)

b= find_second(nums, x)

 

print(a, b)