lower_bound, upper_bound (이분탐색 ) 백준 11663번 선분 위의 점

백준 11663번 문제에서 lower_bound와 upper_bound 적용

문제 요구사항

점 xxx가 선분 [l,r][l, r][l,r]에 포함되는지 확인하려면 l≤x≤rl \leq x \leq rl≤x≤r를 만족해야 합니다. 이를 효율적으로 계산하기 위해 선분의 시작점과 끝점을 각각 정렬하고 이분 탐색을 활용합니다.

적용 방법

1. 정렬된 시작점 배열 (starts)에서 l≤xl \leq xl≤x를 만족하는 시작점의 개수를 upper_bound로 구합니다.
2. 정렬된 끝점 배열 (ends)에서 r<xr < xr<x를 만족하는 끝점의 개수를 lower_bound로 구합니다.
3. 점 xxx를 포함하는 선분의 개수는: {포함 선분 개수} = upper_bound - lower_bound

 

lower_bound와 upper_bound의 차이점과 코드 설명

공통점

1. 둘 다 정렬된 배열을 대상으로 사용됩니다.
2. 둘 다 이분 탐색을 기반으로 동작하여 시간 복잡도는 O(log⁡n)O(\log n)O(logn)입니다.
3. 배열에서 특정 조건을 만족하는 "경계"를 찾는 데 사용됩니다.

 

구현 코드 설명

1. lower_bound 

• 특정 값 이상인 첫 번째 원소의 위치를 찾습니다.
• 찾는 값이 배열에 존재하지 않더라도, 해당 값이 "삽입될 위치"를 반환합니다.

public static int lowerBound(int[] arr, int target) {
    int left = 0, right = arr.length; // 탐색 범위: [left, right)
    while (left < right) {
        int mid = (left + right) / 2; // 중간 위치 계산
        if (arr[mid] < target) {
            left = mid + 1; // target보다 작은 값은 제외
        } else {
            right = mid; // target 이상인 값으로 범위 축소
        }
    }
    return left; // target 이상의 첫 번째 위치 반환
}

 

 

• 동작 원리:
  1. 배열의 중간 위치 mid를 계산합니다.
  2. arr[mid]가 target보다 작으면, mid와 그 왼쪽은 모두 조건에 맞지 않으므로 left = mid + 1로 이동합니다.
  3. arr[mid]가 target 이상이면, right = mid로 이동하여 탐색 범위를 좁힙니다.
  4. 탐색 범위가 하나로 줄어들면 left에 target 이상의 첫 번째 위치가 저장됩니다.

 

2. upper_bound

• 특정 값 보다 큰 첫 번째 원소의 위치를 찾습니다.
• upper_bound는 target\text{target}target까지 포함하지 않고, 그 다음 값의 위치를 반환합니다.

public static int upperBound(int[] arr, int target) {
    int left = 0, right = arr.length; // 탐색 범위: [left, right)
    while (left < right) {
        int mid = (left + right) / 2; // 중간 위치 계산
        if (arr[mid] <= target) {
            left = mid + 1; // target 이하 값은 제외
        } else {
            right = mid; // target보다 큰 값으로 범위 축소
        }
    }
    return left; // target보다 큰 첫 번째 위치 반환
}

• 동작 원리:
  1. 배열의 중간 위치 mid를 계산합니다.
  2. arr[mid]가 target 이하이면, mid와 그 왼쪽은 조건에 맞지 않으므로 left = mid + 1로 이동합니다.
  3. arr[mid]가 target보다 크면, right = mid로 이동하여 탐색 범위를 좁힙니다.
  4. 탐색 범위가 하나로 줄어들면 left에 target보다 큰 첫 번째 위치가 저장됩니다.

 

 

 

 

---

 

right = mid - 1 대신 right = mid를 사용하는 이유?

이분 탐색의 종료 조건과 탐색 범위를 명확히 유지하기 위해서입니다. 

---

1. right = mid와 탐색의 범위 유지

이분 탐색에서 탐색 범위는 보통 반개구간 형태로 설정합니다:

• left는 탐색 범위에 포함됩니다.
• right는 탐색 범위에 포함되지 않습니다.

즉, 탐색 구간은 항상 [left, right) 형태로 유지됩니다.

right = mid의 의미

• mid가 탐색 조건을 만족하는 경우, mid를 포함한 탐색 범위를 유지하려고 right = mid를 설정합니다.
• 이 경우 탐색 구간은 [left, mid)로 좁혀집니다.

왜 right = mid - 1를 쓰지 않나?

• right = mid - 1을 사용하면 mid가 탐색 범위에서 제외됩니다.
• 이는 탐색 범위를 [left, mid) 형태로 유지하지 않고 깨뜨리게 됩니다.
• 반대로, 탐색 구간이 닫힌 구간 [left, right] 형태로 유지되도록 설계한 경우에는 right = mid - 1을 사용할 수도 있습니다.

---

2. right = mid - 1과의 차이

right = mid를 사용할 때

• 탐색 구간이 [left, right)로 유지되며, 현재의 mid 값이 탐색에 포함됩니다.
• 따라서 경계값을 정확히 찾을 때 유리합니다.

right = mid - 1을 사용할 때

• 탐색 구간이 [left, right]로 유지되며, 현재 mid 값이 탐색에서 제외됩니다.
• 이는 특정 값 보다 작은 값만을 찾을 때 적합합니다.