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

 

내가 짠 코드

from bisect import bisect_left, bisect_right

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

class CountOfNum:
    def __init__(self, _N: int, _array, _x:int) -> None:
        self.m_arrayLen = _N
        self.m_array = _array
        self.m_target = _x

    def UseBisect(self) -> int:
        left = bisect_left(self.m_array, self.m_target)
        right = bisect_right(self.m_array, self.m_target)
        if right == left : 
            return -1
        return right - left

    def UseBiSearch(self) -> int:
        left = 0
        right = self.m_arrayLen - 1
        findIdx = -1
        while left < right:
            mid = (left + right) // 2
            if self.m_array[mid] == self.m_target:
                findIdx = mid
                break
            elif self.m_array[mid] > self.m_target:
                right = mid -1
            else:
                left = mid + 1
        
        if findIdx == -1:
            return -1

        leftPtr = findIdx - 1
        rightPtr = findIdx + 1
        total = 1
        while leftPtr >= 0:
            if self.m_array[leftPtr] == self.m_target:
                total += 1
                leftPtr -= 1
            else:
                break
        while rightPtr < self.m_arrayLen:
            if self.m_array[rightPtr] == self.m_target:
                total += 1
                rightPtr += 1
            else :
                break
        return total


con = CountOfNum(N, array, x)
print(con.UseBisect())
print(con.UseBiSearch())

문제 : 두 번째 방법 UseBiSearch에서 먼저 하나의 값을 찾고 두 개의 포인터를 이용하여 개수를 구했다. 개수 구하는 과정을 좀 더 세련되게 진행하려면 두 번의 바이너리를 서치를 진행하여 첫 인덱스, 마지막 인덱스를 구하는 방식을 사용해야 한다.

 

동빈나님 코드

  == 내가 짠 코드 bisect와 유사