[Algorithm] 이진탐색 - 정렬된 배열에서 특정 수의 개수 구하기, 고정점 찾기

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

# 처음 끝 배열 인덱스 찾아서 빼주기
def count_by_value(array, x):
    n = len(array)

    a = first(array, x, 0, n - 1)
    if a == None:
        return 0
    b = last(array, x, 0, n - 1)

    return b - a + 1

# 첫번째 시작 원소 찾기
def first(array, target, start, end):
    if start > end:
        return None
    mid = (start + end) // 2
    # mid == 0 첫번째 원소이거나 mid-1원소 내 왼쪽 원소가 나보다 작으면 그리고 mid 인덱스 배열값이 찾는값이여야함
    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)


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

count = count_by_value(data, x)
if count == 0:
    print(-1)
else:
    print(count)

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)

책에 있는 다른 풀이인데 파이썬스러운 코드인것같다

고정점 찾기

def binary_search(array, start, end):
    if start > end:
        return None
    mid = (start + end) // 2
    if array[mid] == mid:
        return mid
    elif array[mid] > mid:
        return binary_search(array, start, mid - 1)
    else:
        return binary_search(array, mid + 1, end)


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

index = binary_search(array, 0, n - 1)

if index == None:
    print(-1)
else:
    print(index)

시간제한이 O(logN)이 있는 문제였다.
for 문 하나만으로도 시간 복잡도가 O(n)이 되기 때문에 반목문 없이 코드를 짜야해야해서 어려웠다.
1. 문제에서 값이 인덱스와 동일한 원소 하나밖에 없다는걸 전제를 한다. -> 모두 살펴볼 필요가없고 하나만 찾으면 된다.
2.정렬된 배열이기 때문에 mid 인덱스를 기준으로 재귀적으로 이진탐색을 실행한다.

반도체 설계

어렵다...복습시간때...