이진 검색

자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법

이진검색은 이진탐색, 이분탐색이라고도 한다. 목적 키를 찾을 때까지 이진 검색을 순환적으로 반복 수행해, 검색범위를 반으로 줄여가면서 보다 빠르게 검색을 수행한다.

이진 검색의 선행조건

자료가 정렬된 상태여야 한다.

이진 검색의 검색방법

1. 자료의 중앙에 있는 원소 선택
2. 중앙 원소값과 찾고자 하는 목표 값 비교
3. 목표 값<중앙 원소값일 경우 자료 왼쪽 반에 대해 새로 검색 수행
   목표 값>중앙 원소값일 경우 자료 오른쪽 반에 대해 새로 검색 수행
4. 찾고자 하는 값을 찾을 때까지 반복

이진 검색의 시간 복잡도

O(logN)이다. 찾기에 실패할 경우에도 같다.

이진 검색을 자바에서 사용하는 법

Java에서는 이진 검색의 라이브러리 binarySearch를 제공한다.

int [] arr = {1,2,3,4,5,6,7};
Arrays.sort(arr);
int index = Arrays.binarySearch(arr, 3); 
// 배열arr에서 값이 3인 값의 인덱스 선택

lower bound

정렬 상태를 유지한 채 x를 삽입할 수 있는 첫 번째 위치

lower bound의 구현

static int lowerBound(List<Integer> data, int target) {
    int begin = 0;
    int end = data.size();
    
    while(begin < end) {
    	int mid = (begin + end) / 2;
        
        if(data.get(mid) >= target) {
        	end = mid;
        }
        else {
        	begin = mid + 1;
        }
    }
    return end;
}

upper bound

정렬 상태를 유지한 채 x를 삽입할 수 있는 마지막 위치

upper bound의 구현

static int upperBound(List<Integer> data, int target) {
    int begin = 0;
    int end = data.size();
    
    while(begin < end) {
    	int mid = (begin + end) / 2;
        
        if(data.get(mid) <= target) {
        	begin = mid + 1;
        }
        else {
        	end = mid;
        }
    }
    return end;
}