[99클럽 코테 스터디 3일차 TIL] 이분 탐색

 

문제 : https://www.acmicpc.net/problem/11663

 

백준 11663번 선분 위의 점

 

 

풀이

이분 탐색을 활용하는 방법

이진 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘 입니다. 따라서 sort() 메서드를 사용하여 정렬을 우선 해줘야 합니다. 그리고 보통 변수 3개 (start, mid, end)를 사용하여 탐색하게 됩니다.

이분 탐색을 사용할 경우 시간 복잡도는 O(logN)입니다. 단계마다 탐색 범위를 반으로 나누는 것과 동일하므로 O(logN)이라는 시간 복잡도를 가지게 됩니다. 

import sys

read = sys.stdin.readline

def find_start(locations, target):
    start, end = 0, N - 1
    while start <= end:
        mid = (start + end) // 2
        if locations[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
    return start

def find_end(locations, target):
    start, end = 0, N - 1
    while start <= end:
        mid = (start + end) // 2
        if locations[mid] <= target:
            start = mid + 1
        else:
            end = mid - 1
    return start

N, M = map(int, read().split())

locations = list(map(int, read().split()))
locations.sort()

for i in range(M):
    start, end = map(int, read().split())
    start_idx = find_start(locations, start)
    end_idx = find_end(locations, end)

    print(end_idx - start_idx)

 

TIL

이번에는 보자 마자 이분 탐색 알고리즘을 사용하여 풀어야 한다고 생각이 들었고 코드를 바로 작성을 했습니다. find_start 점과 find_end점의 index를 구할 때 조건 문이 조금 다르게 해야한다는 부분에서 시간이 조금 걸렸지만 그래도 쉽게 풀 수 있었던 것 같습니다.

 

이 외에도 다른 방법이 있다면 정보를 공유해주시면 감사하겠습니다.