이진 탐색 ( + 하한 lower_bound, 상한upper_bound )

1. 이진 탐색 

• 정렬된 데이터에서 특정 값을 찾는 알고리즘
• 탐색 범위를 반으로 줄여가며 찾기 떄문에 O(lgN) 으로 빠르게 동작한다. 
• 만약 정렬된 데이터에 찾고자하는 수가 중복으로 있다면 가장 왼쪽의 원소를 찾는 방법을 lower bound 라 하며, 가장 오른쪽 원소의 다음 위치를 반환하는 방법을 upper bound라고 한다. 
  • 수열 {1, 2, 3, 3, 3, 4} 에서 3의 lower bound는 인덱스 2, uppder bound는 5다. 
• 비슷하게 데이터를 반으로 분할하는 알고리즘으로 분할정복이 있다.
• 하지만 분할정복은 문제를 부분적으로 해결하는 알고리즘으로 탐색이 목적이 아니다.

 

2. 탐색 과정

1. 탐색 범위 low ~ high를 정하고 low <= high 조건을 만족하는 동안 루프를 수행
2. 루프에서 탐색 범위가 low > high 될 때까지 범위를 줄여나간다.
   1. 탐색 범위 low ~ high의 배열의 중간 값 mid = (low + high)/2를 구한다.  
   2. 중간 인덱스 값 mid와 key 값을 비교한다. (key는 탐색하고자 하는 값)
   3. 중간 값이 key보다 크다면 key는 중간값보다 왼쪽 영역에 존재,
      중간 값이 key 보다 작다면 key는 오른쪽 영역에 존재한다. 
      
      1. 왼쪽 탐색 시 범위 수정: high = mid - 1
      2. 오른쪽 탐색 시 범위 수정: low = mid + 1
   4. 이 과정을 반복하며 key 값이 있을 수 있는 범위를 줄여나간다. 
   5. key 값이 중간 인덱스 값과 같다면 탐색 종료! 

 

구현

    static int binarySearch(int key) {
        int low = 0;
        int high = arr.length-1;
        
        while(low <= high) {
            int mid = (low+high)/2;
            if(key == arr[mid]) {
                return mid;
            }else if(key < arr[mid]){
                high = mid - 1;
            }else {
                low = mid + 1;
            }
        }
        
        // key가 없다. 
        return -1;
    }

 

 

3. 수열에 중복 key 탐색

• 이진 검색해서 중복된 Key가 있을때, upper_bound 또는 lower_bound 를 기준으로 탐색할 수 있다. 
• upper_bound
  • 목표 값 이상의 값을 처음으로 만나는 위치
• lower_bound
  • 찾고자 하는 값 초과한 값을 처음 만나는 위치

 

• 위 그림에서 key 3의 lower bound는 4번째, upper bound는 7번째가 된다.

 

 

 

구현하는데 헷갈렸던 점

1) key <= mid값 일 때, high를 줄이는 것 

mid값을 '예상 key값'으로 이해하면, mid값이 key값보다 크면, high를 mid로 줄여 key가 있을 수 있는 범위를 줄인다. 

 

2) 만약 범위에 속하는 key가 존재하지 않는 경우도 주의하기 

key값이 존재하지 않으면,

 - 배열 길이 값(범위 초과)이 리턴되거나 ( lower + upper )

 - key보다 큰 값의 위치가 리턴된다. 이상을 찾는 lower의미가 달라짐 (lower bound)

   따라서, 배열[key] 값과 배열[리턴된 위치의 값]이 일치하는지 확인하여 lower_bound가 제대로 작동하는지 알 수 있다. 

 

 

 

 

참고 및 출처

https://jackpot53.tistory.com/33?category=715474

http://bajamircea.github.io/coding/cpp/2018/08/09/lower-bound.html

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