[JAVA] 이진탐색 lowerbound, upperbound 정리

 

 

Lower bound, Upper bound란?

 

그림을 보면 쉽게 이해할 수 있다. 

• lower bound: 찾고자 하는 값이 처음 나타나는 위치
• upper bound: 찾고자 하는 값 바로 뒤 위치

 

 

원래 이진탐색 코드

//오름차순 정렬된 arr에서 target값을 찾아 인덱스를 반환하는 함수
private int findIdx(int[] arr, int target) {
    int start = 0;
    int end = arr.length;

    while (start < end) {

      int mid = (start + end)/2;

      if (arr[mid] == target)
        return mid;

      if (arr[mid] < target)
        start = mid+1;
      else //arr[mid] > target
        end = mid;
    }

    return -1;
}

• 오름차순 정렬된 arr을 넣었을 때 값이 있는지 확인하고, 값이 있으면 해당 인덱스를 반환하는 함수를 구현하였다
• arr[mid] 가 target과 같을 때 해당 인덱스를 반환한다
• 중복값이 없는 경우 유용하게 쓰일 수 있음

 

 

 

이진탐색에서 lower bound 찾기

private static int findIdx(int[] arr, int target) {
    int start = 0;
    int end = arr.length;

    while (start < end) {
      int mid = (start + end)/2;

      if (arr[mid] < target)	//point***
        start = mid+1;
      else //arr[mid] >= target
        end = mid;
    }

    return start;
}

• 값이 target값과 같아도 왼쪽으로 이동하여 가장 첫 번째로 나온 값을 찾는다

 

<3을 찾는 경우>
[ 1,2,3,3,3,4 ]    =>   결과: 2
[ 1,2,2,2,2 ]    =>   결과: 5  (index outofrange)
[ 4,5,6,7 ]   =>   결과: 0

• lower bound 방식은 중복값이 있을 때 유용하다
• 중복값이 있을 땐 가장 첫 번째로 등장하는 idx를 찾아주고
• 값이 없을 땐 값이 삽입되어야할 위치를 반환한다

 

 

 

이진탐색에서 upper bound 찾기

private static int findIdx(int[] arr, int target) {
    int start = 0;
    int end = arr.length;

    while (start < end) {
      int mid = (start + end)/2;

      if (arr[mid] <= target)	//point***
        start = mid+1;
      else //arr[mid] > target
        end = mid;
    }

    return start;
}

• lower bound와 달라진 점이 등호(=)밖에 없다
• 같은 값을 찾아도 오른쪽으로 이동하여 계속 찾는다

 

<3을 찾는 경우>
[ 1,2,3,3,3,4 ]    =>   결과: 5
[ 1,2,3,3,3 ]    =>   결과: 5  (index outofrange)
[ 4,5,6,7 ]   =>   결과: 0

• 중복값이 있을 경우 (마지막으로 등장하는 인덱스)+1을 찾아주고
• 값이 없으면 해당 값이 삽입되어야할 위치를 반환한다

 

 

 

 

활용방법 논의

upperbound와 lowerbound는 확실하게 내가 원하는 값을 꺼내올 수 있어서 이진탐색 시 잘 활용될 것 같다.

1. 리스트에 값이 있는지 확인
2. 리스트에 값이 없을 때 내가 삽입되어야할 위치 확인
3. 리스트에 값을 찾고, 중복값의 개수 세기 (upper-lower 범위로 구하면 됨)

 

 

 

 

 

참고블로그

https://st-lab.tistory.com/267

[백준] 10816번 : 숫자 카드 2 - JAVA [자바]