이진 검색이란?
이진 검색은 선형 검색과 다르게 키값으로 이미 정렬되어 있는 상태로
선형 검색보다 빠르게 검색할 수 있다는 장점이 있다.
(오름차순 또는 내림차순 등)
이진 검색은 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘이다.
그림과 같이 5를 검색하는 과정을 살펴보면 먼저 배열 중앙에 위치한 7부터 검색을 시작한다.
검색할 값은 5, 7은 5보다 크다. 따라서 검색의 범위를 배열의 앞부분으로 줄인다.
그리고 다음 검색할 범위의 중앙에 위치한 요소를 선택하여 검색을 시작한다.
검색할 값 5는 3보다 크다. 그러므로 검색 범위의 뒷부분만 다시 검색한다.
이러한 과정을 거쳐 탐색에 성공한다.
그럼 어떻게 앞, 중간, 끝을 알 수 있는지 알아보자.
pl : 맨 앞 인덱스
pc : 중간 인덱스
pr : 맨 끝 인덱스
이런식으로 포인터를 만들어 사용할 것이다. 코드로 한번 보면 이해가 빠를 것이다.
public int binSearch() {
int n = 7; // 배열의 길이를 입력받음
int[] a = new int[n]; // 배열 생성
int pl = 0; // 맨 앞 인덱스
int pr = n - 1; // 맨 끝 인덱스
do {
int pc = (pl + pr) / 2; // 중앙 인덱스
if(a[pc] == key) { // 현재 중앙 인덱스 요소와 찾을 key가 같은 경우
return pc;
} else if(a[pc] < key) { // 현재 중앙 인덱스 요소가 찾을 key보다 작은 경우
pl = pc + 1; // 검색 범위를 뒤 쪽 절반으로 줄임
} else { // 현재 중앙 인덱스 요소가 찾을 key보다 큰 경우
pl = pc - 1; // 검색 범위를 앞 쪽 절반으로 줄임
}
} while(pl <= pr); // 맨 앞 인덱스가 맨 끝 인덱스보다 작거나 같은 경우 반복 중지
return -1; // 검색이 실패한 경우
}
- 배열의 길이는 7, 맨 앞 인덱스, 맨 끝 인덱스는 최초에 0과 n - 1로 설정
- do-while문을 사용하여 최초 1회 실행
- pc 변수를 중앙 인덱스로 사용하기 위해 (pl + pr) / 2 로 설정
- 조건에 따라 같은 경우는 pc를 반환 (같은 경우엔 검색 성공)
- 배열의 중간 인덱스 요소(pc)가 key보다 작으면 검색 범위를 뒤쪽 절반으로 줄임
- 그게 아닌 경우(a[pc]가 key보다 크면) 검색 범위를 앞 쪽 절반으로 줄임
위와 같이 알고리즘을 구성하면 이진 검색이 가능하다. 선형 검색에 비해 매우 효율적이다.
하지만 코드가 선형 검색에 비해 많이 복잡해 보인다. 그래서 java에서는 이진 검색을 하는
메서드를 표준 라이브러리로 제공한다.(직접 이진 검색을 구현할 필요가 없다.)
binarySearch
바로 java.util.Arrays 클래스의 binarySearch 메서드다.
binarySearch 메서드를 사용하면 2가지 장점이 있다.
- 이진 검색 메서드를 직접 구현할 필요가 없다.
- 배열 요소의 자료형과 관계없이 검색할 수 있다.
binarySearch 메서드는 오름차순으로 정렬된 배열을 가정하고 값이 key 요소를 검색한다.
자료형에 관계없이 사용할 수 있도록 자료형에 따라 오버로딩 되어 있다.
검색에 성공한 경우 key와 일치하는 요소의 index를 반환한다.
검색에 실패한 경우 key보다 큰 요소 중 첫 번째 요소의 인덱스를 반환한다.
만약 배열의 요소가 전부 key보다 작은 경우에는 배열의 길이를 반환한다.
binarySearch 메서드를 사용하여 이진 검색 해보기
public static void main(String[] args) {
int x = new int[10];
int key = 7;
// 배열 x에 요소를 추가함....
int idx = Arrays.binarySearch(x, key); // 검색 실패시 음수로 반환됨
if(idx < 0) { // 0보다 작다는 조건으로 실패 처리가 전부 가능
System.out.println("그 값에 요소가 없습니다.");
} else {
System.out.println("그 값은 x[" + idx + "]에 있습니다,");
}
}binarySearch 메서드를 사용하니 직접 이진 검색을 구현하지 않고도 쉽게 결과를 얻을 수 있다.
