📚 Collections.binarySearch()
public static <T>
int binarySearch(List<? extends Comparable<? super T>> list, T key) {
if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
return Collections.indexedBinarySearch(list, key);
else
return Collections.iteratorBinarySearch(list, key);
}
Collections의 binarySearch()는 정렬된 리스트 list에서 값 key의 위치를 이분 탐색으로 찾는 메서드다.
값이 존재하면 해당 인덱스를 반환하고, 없으면 삽입해야 할 위치를 -(삽입위치 + 1) 형태로 반환한다.
- 매개변수로 받은 list가 RandomAccess를 implements하고 있는지
- 리스트 크기에 대한 임계점(5000)인
BINARYSEARCH_THRESHOLD보다 작은지
확인하고 indexedBinarySearch()를 호출할 것인지, iteratorBinarySearch()를 호출할 것인지 결정한다.
RandomAccess
ArrayList.java
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable { }
Vector.java
public class Vector<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable { }
LinkedList.java
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable { }
RandomAccess는 Marker Interface(표식 인터페이스)로, List 구현체가 빠른 인덱스 기반 접근이 가능한지 여부를 나타낸다.
💡 Marker Interface란?
아무 메서드도 선언되어 있지 않고, 자신을 구현하는 클래스가 특정 속성을 가짐을 표시하는 인터페이스
ArrayList나 Vector처럼 내부적으로 배열을 사용해 데이터를 저장하는 컬렉션은 인덱스를 이용한 접근이 빠르기 때문에 RandomAccess 인터페이스를 구현한다.
반면에 LinkedList는 순차적으로 노드를 따라가야 원하는 위치에 접근할 수 있어 인덱스 기반 접근이 느리며 RandomAccess를 구현하지 않는다.
이 부분은 ArrayList vs LinkedList에 더 자세하게 나와있다.
즉, RandomAccess를 구현한 List는 인덱스 기반 반복(get(i))을 해도 성능 문제가 없지만, 구현하지 않은 경우에는 Iterator 기반 반복문(for-each문)을 사용해야 한다.
또한 5000 이상, 즉 BINARYSEARCH_THRESHOLD 이상일 경우 iterator를 통해 찾게 된다.
If the specified list does not implement the {@link RandomAccess} interface and is large, this method will do an iterator-based binary search that performs O(n) link traversals and O(log n) element comparisons.
Collections.indexedBinarySearch()
private static <T>
int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key) {
int low = 0;
int high = list.size()-1;
while (low <= high) {
int mid = (low + high) >>> 1; // (low + high) / 2
Comparable<? super T> midVal = list.get(mid);
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
}
- 빠른 인덱스 기반 접근이 가능한 리스트(RandomAccess)이거나
- 리스트의 크기가 5000 미만인 경우
indexedBinarySearch()가 호출된다.
주어진 key의 인덱스를 찾는 함수로, 이때 key와 리스트의 요소는 모두 Comparable 인터페이스를 구현한 객체여야 한다.
전체적인 흐름은 우리가 일반적으로 아는 이분 탐색과 같다.
리스트의 중간 값인 midVal이 입력 받은 key와 비교 : compareTo() 사용
- 0보다 작은 값 ->
midVal이key보다 작다 - 0보다 큰 값 ->
midVal이key보다 크다 - 0 -> 두 값이 같다
탐색이 끝난 후 key를 찾았다면 해당 인덱스를 return 하고, key가 리스트에 없다면 low가 key가 삽입될 위치를 -(low + 1) 형식으로 return 한다.
Collections.iteratorBinarySearch()
private static <T>
int iteratorBinarySearch(List<? extends Comparable<? super T>> list, T key)
{
int low = 0;
int high = list.size()-1;
ListIterator<? extends Comparable<? super T>> i = list.listIterator();
while (low <= high) {
int mid = (low + high) >>> 1; // (low + high) / 2
Comparable<? super T> midVal = get(i, mid);
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
}
빠른 인덱스 기반 접근이 불가능한 리스트(not RandomAccess)이고, 리스트의 크기가 5000 이상인 경우 iteratorBinarySearch()가 호출된다.
이 메소드는 인덱스 기반 접근 대신 iterator를 활용해서 이분 탐색을 수행한다.
ListIterator<? extends Comparable<? super T>> i = list.listIterator();i는 리스트의 순차 접근을 위한 ListIterator로, get(i, mid)를 이용해서 mid 인덱스까지 Iterator로 순차 접근해서 요소를 가져온다.
(indexedBinarySearch()는 list.get(mid) 사용)
뒷 로직은 indexedBinarySearch()와 같으며, 따라서 두 메서드의 본질적인 차이는 리스트 요소에 접근하는 방식에 있다.
