Arrays클래스내에 자료형에 상관없이 오버로딩 돼 있는 binarySearch()메서드가 존재한다.
이진 검색의 논리상 이미 정렬된 배열을 매개변수로 넣어줘야 한다. 그럼 알고리즘이 알아서 중앙값을 바꿔가며 평균 2/n의 속도로 배열에서 내가 원하는 값을 찾아준다.
public static int binarySearch(int[] a, int key) {
return binarySearch0(a, 0, a.length, key);
}T[]는 무조건 정렬된 배열을, key는 내가 찾고싶은 값을 인자로 넘겨주면 된다.
- 이진 검색 메서드를 직접 작성할 필요가 없다.
- 배열 요소의 자료형과 관계없이 검색할 수 있다.
- https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Arrays.html#binarySearch(int[],int) int형 배열의 binarySearch()
검색 성공
해당 메서드는 검색에 성공한 경우 key와 일치하는 요소의 인덱스값을 반환합니다. key와 일치하는 요소가 여러 개 있을 경우 어느 요소의 인덱스를 반환하는지는 정해져 있지 않기에 필요하다면 아래 코드처럼 그 인덱스 앞에 또 내가 원하는 값이 있는지 확인 해 줄 수 있겠습니다.
int[] arr = {1,2,3,5,5,5,5,6,7,8}; // 5가 여러개인 int배열
int key = 5; // 찾고자 하는 값임.
int binarySearchFirstIndex(int[] intArray, key) {
int index = Arrays.binarySearch(intArray, 5);
// 메서드로 arr안의 5 인덱스 아무거나 한 개 가져옴. 이 코드에선 4가 유력.
for(int i = index - 1; i >= 0; i--) {
if(intArray[i] == key) {
index = i;
// 만약 binarySearch()메서드에서 반환한 인덱스보다 더 앞 인덱스에서
// key값을 발견했다면 index에 i를 대입함. for문에는 영향을 주지 않기에 괜찮다.
} else {
break;
}
}
return index; // 결과적으로 배열에서 맨 앞 key의 인덱스를 반환하게 된다.
}검색 실패
해당 메서드는 검색에 실패했을 경우에 '배열 안에 key가 있어야 할 위치(삽입 포인트)를 추정할 수 있는 값'을 반환한다. 삽입 포인트가 x라고 할 때 반환값은 -x - 1이 된다. 검색하기 위해 지정한 key보다 큰 요소 중 첫 번째 요소의 인덱스이다. 해당 인덱스의 배열에 key를 삽입하면 다시 검색 시 새로 배열 정렬을 실행하지 않아도 정렬된 배열처럼 사용할 수 있다.
int[] arr = {0,1,2,3,5,6,7,8,9,10}; // 4가 없다.
Arrays.binarySearch(arr, 4); // 4를 검색한다.위 코드는 4가 없지만 binarySearch로 4를 검색한 경우 요소 5의 인덱스는 4이다
-4 -1이 되므로 -5가 반환된다. -가 안붙었으면 검색에 성공한 것이다.
Arrays.binarySearch(arr, 11); // 11검색만약 위 코드처럼 11을 검색하면 이는 배열의 마지막 요소인 10보다 크기에 배열의 크기인 10이 삽입 포인트로 설정되고, -10 -1하여 -11이 반환됩니다.
배열이 참조형으로 이루어진 경우,
binarySearch()는 총 9개가 오버로딩 돼 있는데, 이 중 마지막인 2개는 객체를 이진검색할 때 사용합니다.
static int binarySearch(Object[] a, Object key)
// 자연 정렬이 된 배열에서 요소의 대소 관계를 판단하고 검색한다. 따라서 정수 배열, 문자열 배열에서 검색할 때 적당하다.
private static int binarySearch0(Object[] a, int fromIndex, int toIndex,
Object key) {
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
@SuppressWarnings("rawtypes")
Comparable midVal = (Comparable)a[mid];
@SuppressWarnings("unchecked")
int cmp = midVal.compareTo(key);
if (cmp < 0)
low = mid + 1;
else if (cmp > 0)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}위 처럼 compareTo()메서드를 사용하기 때문에 객체가 Comparable을 구현해야 한다.
static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)
// 자연 정렬이 아닌 순서로 나열된 배열에서 검색하는 메서드이다. 자연 정렬을 논리적으로 갖지 않는 클래스의 배열에서 검색할 때 알맞다.
private static <T> int binarySearch0(T[] a, int fromIndex, int toIndex,
T key, Comparator<? super T> c) {
if (c == null) {
return binarySearch0(a, fromIndex, toIndex, key);
}
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
T midVal = a[mid];
int cmp = c.compare(midVal, key);
if (cmp < 0)
low = mid + 1;
else if (cmp > 0)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}이렇게 Comparable을 구현하지 않은 참조형 객체들은, 따로 Comparator c를 지정해 주어야 한다.
