[자료구조] 검색
검색 종류
- 배열 검색
- 선형 리스트 검색
- 이진검색트리 검색
배열 검색 알고리즘
- 선형 검색 : 무작위로 늘어놓은 데이터 모임에서 검색을 수행
- 이진 검색 : 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색을 수행
- 해시법 : 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행
- 체인법 : 같은 해시 값의 데이터를 선형 리스트로 연결하는 방법
- 오픈 주소법 : 데이터를 위한 해시 값이 충돌할 때 재해시하는 방법
데이터 집합이 있을 때 검색만 하는 경우는 계산 시간이 짧은 알고리즘을 사용하면 된다. 하지만 추가,삭제 등을 해야하는 경우에는 검색 이외의 작업에 소요되는 비용을 종합해서 판단해야 한다. 데이터 추가 비용이 많이 들어가면 피해야한다.
선형 검색
검색 중 가장 기본적인 알고리즘.
원하는 키 값을 갖는 요소를 만날 때까지 맨앞부터 순서대로 요소를 검색하면 된다.
검색 종료 조건
- 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우
- 검색할 값과 같은 요소를 발견한 경우
검색 속도
요솟수가 n개면 최악의 경우 n번을 다 확인을 해야한다.
보초법
선형 검색은 검색 종료 조건 모두를 판단한다. 이 비용을 반으로 줄이는 방법이 보초법(sentinel method)다.
검색하기 전에 검색하고자 하는 키 값을 맨 끝 요소에 저장한다. 이때 저장하는 값을 보초라고 한다.
검색된 대상이 마지작에 추가한 보초 값이면 종료 조건 1번을 만족하게 되는 것이다. 실제 코드에서는 2번 조건만 종료 조건이 되는 셈이다.
이진 검색
이 알고리즘의 전재 조건은 정렬되어 있다는 것이다. 선형 검색보다 빠르다.
중앙값을 기준으로 찾고자 하는 값이 중앙값보다 크면 검색 범위를 중앙값의 오른쪽으로 잡고 작다면 왼쪽으로 잡는다. 이를 반복하면 찾고자하는 대상을 찾을 수 있다.
선형 검색의 시간 복잡도는 O(n) 이고 이진 검색의 시간 복잡도는 O(logn) 이 된다.
요솟수가 1024개일 때 선형 검색은 최악의 경우 1024번 검색을 해야하지만 이진 검색을 사용하면 10번 안에 찾을 수 있다.
binarySearch
Java는 배열에서 이진 검색을 하는 메서드를 표준 라이브러리로 제공한다.
java.util.Arrays 클래스의 binarySearch 메서드가 있다.
- 검색에 성공한 경우: 일치하는 요소의 인덱스 반환 ( 여러 개일 경우 무작위 반환)
- 검색에 실패한 경우: 삽입 포인트 -1 을 반환 ( 배열의 모든 요소가 key보다 작을 경우 배열의 길이를 삽입 포인트로 정함)
static int binarySearch(Object[] a, Object key)
- 자연 정렬이라는 방법으로 요소의 대소 관계를 판단한다.
- 자연 정렬이란 => 1,100,1000,2,20 이렇게 정렬하는 것이 아니라 1, 2, 20, 100, 10000 이렇게 정렬하는 것을 의미
- 정수, 문자열 배열을 검색할 때 적당
static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)
- 자연 정렬로 정렬되지 않은 배열에서 검색
java.util.Comparator
객체의 대소 관계를 판단한다.
comparator 직접 구현
Comparator인터페이스를 구현한 클래스를 정의하고 그 클래스형의 인스턴스를 생성- 매개변수로 전달된 두 객체의 대소 관계를 비교하여 그 결과를 반환하는
compare메서드를 구현
기본 예제
private static class Comp implements Comparator<T> {
public int compare(T d1, T d2) {
if(d1 > d2){
return 양수;
}
if(d1 <> d2){
return 음수;
}
if(d1 == d2){
return 0;
}
}
}