Java의 기본 라이브러리에는 Binary Search 메서드가 내장되어 있습니다.
java.util.Arrays 클래스에 존재합니다.
다양한 자료형의 배열을 사용할 수 있에 오버로딩되어 있는데,
본 아티클에서는, 제너릭스로 구현된(자료형에 구애받지 않고 사용할 수 있게 구현) 메서드를 사용해볼 것입니다..
새로운 자료형(클래스) 제너릭스로 구현
//--- 신체검사 데이터 ---//
class PhyscData {
private final String name; // 이름
private final int height; // 키
private final double vision; // 시력
//--- 생성자(constructor) ---//
public PhyscData(String name, int height, double vision) {
this.name = name;
this.height = height;
this.vision = vision;
}
//--- 문자열로 만들어 반환하는 메서드 --//
public String toString() {
return name + " " + height + " " + vision;
}
//--- 키의 오름차순으로 정렬하기 위한 comparator ---//
public static final Comparator<PhyscData> HEIGHT_ORDER =
new HeightOrderComparator();
private static class HeightOrderComparator implements Comparator<PhyscData> {
public int compare(PhyscData d1, PhyscData d2) {
return (d1.height > d2.height) ? 1 :
(d1.height < d2.height) ? -1 : 0;
}
}
}
PhyscData라는 자료형에 대해 Binary Search를 사용하려고 합니다.
PhyscData라는 클래스 내부에 Comparator를 하나 구현했습니다. (외부에 구현해도 상관 없습니다.)
그리고 구현한 Comparator 내부에는 compare라는 메서드를 구현해야 합니다.
PhyscData 객체들의 순서를 비교할 때, height를 기준으로 하며,
더 큰 height를 가진 객체가 오른쪽에 오도록(오름차순) 정렬 규칙을 정한 것입니다.
binarySearch 메서드 사용
class BinarySearch1 {
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
PhyscData[] x = { // 키의 오름차순으로 정렬
new PhyscData("강민하", 162, 0.3),
new PhyscData("이수연", 168, 0.4),
new PhyscData("황지안", 169, 0.8),
new PhyscData("유서범", 171, 1.5),
new PhyscData("김찬우", 173, 0.7),
new PhyscData("장경오", 174, 1.2),
new PhyscData("박준서", 175, 2.0),
};
System.out.print("키가 몇 cm인 사람을 찾고 있나요?: ");
int height = stdIn.nextInt(); // 킷값을 읽어 들임
int idx = Arrays.binarySearch(
x, // 배열 x에서
new PhyscData("", height, 0.0), // 키가 height인 요소를
PhyscData.HEIGHT_ORDER // HEIGHT_ORDER에 의해 검색
);
if (idx < 0)
System.out.println("그 값의 요소가 없습니다.");
else {
System.out.println("그 값은 x[" + idx + "]에 있습니다.");
System.out.println("찾은 데이터: " + x[idx]);
}
}
}위의 코드는 PhyscData의 배열에서 Binary Search를 실행하고 있습니다.
Arrays.binarySearch 메서드의 인자로 배열, key값, Comparator를 구현한 객체가 들어감을 확인할 수 있습니다.
만약 찾는 값이 존재한다면, 위치(인덱스)를 반환합니다.
존재하지 않는다면, 만약 값이 존재한다면 어디에 위치해야하는지를 알려주는 값을 음수로 반환합니다.
이를 삽입 포인트(insertion point)라고 하는데,
insertioin point = -(원래 위치했어야 하는 인덱스 값) - 1 로 주어집니다.
만약 배열이 Comparator에 정의된 compare 메서드의 규칙에 따라 정렬되어 있지 않다면,
정확하지 않은 값을 반환합니다.
binarySearch 메서드는 정렬이 된 배열을 가정하고 검색을 실행하기 때문입니다.
내림차순으로 수정해보기
package chapter3;// 신체검사 데이터 배열에서 이진 검색
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
class BinarySearch1 {
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
PhyscData[] x = { // 시력의 내림차순으로 정렬
new PhyscData("박준서", 175, 2.0),
new PhyscData("유서범", 171, 1.5),
new PhyscData("장경오", 174, 1.2),
new PhyscData("황지안", 169, 0.8),
new PhyscData("김찬우", 173, 0.7),
new PhyscData("이수연", 168, 0.4),
new PhyscData("강민하", 162, 0.3),
};
System.out.print("시력이 몇인 사람을 찾고 있나요?: ");
double vision = stdIn.nextDouble(); // 킷값을 읽어 들임
int idx = Arrays.binarySearch(
x, // 배열 x에서
new PhyscData("", 0, vision), // 시력이 vision인 요소를
PhyscData.VISION_ORDER // HEIGHT_ORDER에 의해 검색
);
if (idx < 0)
System.out.println("그 값의 요소가 없습니다.");
else {
System.out.println("그 값은 x[" + idx + "]에 있습니다.");
System.out.println("찾은 데이터: " + x[idx]);
}
}
}
//--- 신체검사 데이터 ---//
class PhyscData {
private final String name; // 이름
private final int height; // 키
private final double vision; // 시력
//--- 생성자(constructor) ---//
public PhyscData(String name, int height, double vision) {
this.name = name;
this.height = height;
this.vision = vision;
}
//--- 문자열로 만들어 반환하는 메서드 --//
public String toString() {
return name + " " + height + " " + vision;
}
//--- 시력의 내림차순으로 정렬하기 위한 comparator ---//
public static final Comparator<PhyscData> VISION_ORDER =
new HeightOrderComparator();
private static class HeightOrderComparator implements Comparator<PhyscData> {
public int compare(PhyscData d1, PhyscData d2) {
return (d1.vision < d2.vision) ? 1 :
(d1.vision > d2.vision) ? -1 : 0;
}
}
}시력의 내림차순으로 정렬된 배열에서 이진 탐색을 수행하도록 코드를 수정했습니다.
입력을 받는 자료형을 double로 바꾸고,
Comparator의 compare 메서드가 vision을 기준으로,
그리고 반대 방향으로 정렬을 수행하도록 수정했습니다.
System.out.println("idx: " + idx);위와 같은 코드를 추가하여 idx의 값을 살펴봅시다.
idx는 -5가 됩니다.
만약 0.77이 존재했다면 idx가 4였을 것이므로,
(-4) - 1 = -5 의 값이 나온 것입니다.
PhyscData[] x = { // 시력의 내림차순으로 정렬
new PhyscData("박준서", 175, 2.0),
new PhyscData("유서범", 171, 1.5),
new PhyscData("장경오", 174, 1.2),
new PhyscData("김찬우", 173, 0.7),
new PhyscData("황지안", 169, 0.8),
new PhyscData("이수연", 168, 0.4),
new PhyscData("강민하", 162, 0.3),
};이번에는 위와 같이 내림차순의 순서를 망가뜨리고 프로그램을 실행해보겠습니다.
망가진 순서 이전의 값은 탐색이 잘 됩니다.
하지만 망가진 순서 이후의 값은 잘 탐색이 되지 않습니다.
즉, Arrays.binarySearch 메서드는
정렬이 잘 되어 있는지를 따로 확인하지 않고,
정렬이 잘 되어 있다고 가정한 채로 탐색을 수행한 결과를 반환합니다.
감사합니다.