3. 검색 알고리즘
검색은 특정 항목에 주목한다는 공통점이 있다.
키(key) : 주목하는 항목
ex) 국적을 검색할 땐 국적이 키, 나이를 검색할 땐 나이가 키
데이터가 단일 값이면 그대로 키 값이 되겠지만 대부분의 경우에서 키는 데이터의 '일부'이다.
검색 과정
1. 키 값과 일치하도록 지정한다. (한국)
2. 키 값의 구간을 저장한다. (21세 이상 27세 미만)
3. 키 값과 비슷하도록 지정한다. (발음이 가장 비슷한 이름)
조건은 하나만 지정하기도 하지만 논리곱이나 논리합을 사용해 여러 조건을 복합해서 지정하기도 한다.
배열에서 검색
선형 리스트에서 검색
이진 트리 검색
1. 선형 검색 : 무작위로 늘어서 있는 데이터 모임에서 검색을 수행한다.
2. 이진 검색 : 일정한 규칙으로 늘어서 있는 데이터 모임에서 아주 빠른 검색을 수행한다.
3. 해시법 : 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행한다.
- 체인법 : 같은 해시값의 데이터를 선형 리스트로 연결하는 방법
- 오픈 주소법 : 데이터를 위한 해시값이 충돌할 때 재해시하는 방법
해시법은 검색뿐만 아니라 추가나 삭제 등을 효율적으로 수행할 수 있는 종합적인 방법이다.
검색만 할 경우 계산 시간이 짧은 알고리즘을 선택하면 되지만 검색뿐만 아니라 데이터를 추가하거나 삭제하는 작업을 자주 한다면
검색 이외의 소요되는 비용을 평가해 알고리즘을 선택해야 한다.
※ 추가 비용이 큰 알고리즘은 피해야 한다.
선형 검색
- 검색 알고리즘 중 기본적인 알고리즘
- 요소가 직선 모양으로 늘어선 배열에서 검색을 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색하는 방법이다.
'선형 검색(Linear Search)' 또는 '순차 검색(Sequential Search)' 라고 한다.
선형 알고리즘 코드
import java.util.Scanner;
public class SeqSearch {
static int seqSearch(int[] a, int n, int key) {
int i = 0;
while(true) {
if(i == n)
return -1; // 검색 실패(-1을 반환)
if(a[i] == key)
return i; // 검색 성공(인덱스를 반환)
i++;
}
// for문으로 구현할 경우
// for(int i = 0; i < n; i++)
// if(a[i] == key)
// return i;
// return -1;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("요소수 : ");
int num = scanner.nextInt();
int[] x = new int[num]; // 요소수가 num인 배열
for(int i = 0; i < num; i++) {
System.out.print("x[" + i + "]: ");
x[i] = scanner.nextInt();
}
System.out.print("검색할 값: "); // 키 값을 입력 받는다.
int key = scanner.nextInt();
int idx = seqSearch(x, num, key); // 배열 x에서 값이 key인 요소를 검색
if(idx == -1)
System.out.println("그 값의 요소가 없습니다.");
else
System.out.println("그 값은 x[" + idx + "]에 있습니다.");
}
}
선형 검색의 종료 조건
1. i == n이 성립하는 경우
2. a[i] == key가 성립하는 경우
종료 조건을 검사하는 비용은 결코 무시할 수 없다.
이 비용을 반으로 줄이는 방법이 '보초법'이다. 원래 배열에 데이터를 넣어 놓고 맨 끝에 배열을 하나 추가해 검색하는 것.
만일 보초인 배열까지 검색하면 '검색할 값과 같은 요소를 발견했는가'가 성립하기 때문에 i == n이 성립하는 경우의 조건은 없어도 된다.
보초법 선형 알고리즘 코드
import java.util.Scanner;
public class SeqSearchSen {
static int seqSearch(int[] a, int n, int key) {
int i = 0;
a[n] = key; // 보초를 추가
while(true) {
if(a[i] == key)
break;
i++;
}
return i == n ? -1 : i;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("요소수 : ");
int num = scanner.nextInt();
int[] x = new int[num + 1]; // 요소수가 num인 배열
for(int i = 0; i < num; i++) {
System.out.print("x[" + i + "]: ");
x[i] = scanner.nextInt();
}
System.out.print("검색할 값: "); // 키 값을 입력 받는다.
int key = scanner.nextInt();
int idx = seqSearch(x, num, key); // 배열 x에서 값이 key인 요소를 검색
if(idx == -1)
System.out.println("그 값의 요소가 없습니다.");
else
System.out.println("그 값은 x[" + idx + "]에 있습니다.");
}
}
이진 검색
이 알고리즘을 적용하는 전제 조건 : 데이터가 키 값으로 이미 정렬되어 있다는 것을 만족해야 한다.
장점 : 선형 검색보다 좀 더 빠르게 검색할 수 있다.
요소가 오름차순, 내림차순으로 정련된 배열에서 검색하는 알고리즘
a[pc] < key 일 때
- key 보다 작은 것이 분명하므로 검색 대상에서 제외한다.
- a[pc]보다 뒤쪽인 a[pc + 1] ~ a[pr]로 좁힌다. 이를 위해 pl 값을 pc + 1로 수정한다.
a[pc] > key 일 때
- a[pc] ~ a[pr]은 key보다 큰 것이 분명하므로 검색 대상에서 제외한다.
- 검색 범위를 중앙 요소 a[pc]보다 앞쪽인 a[pl] ~ a[pc - 1]로 좁힌다. 이를 위해 pr 값을 pc - 1로 수정한다.
이진 검색의 종료 조건
1. a[pc]와 key가 일치한다.
2. 검색 범위가 더이상 없다.
이진 검색 알고리즘 코드
import java.util.Scanner;
public class BinSearch {
// 요솟수가 n개인 배열 a에서 key와 같은 요소를 이진 검색
static int binSearch(int [] a, int n, int key) {
int pl = 0; // 검색 범위의 첫 인덱스
int pr = n - 1; // 검색 범위의 끝 인덱스
do {
int pc = (pl + pr) / 2; // 중앙 요소의 인덱스
if(a[pc] == key)
return pc; // 검색 성공
else if(a[pc] < key)
pl = pc + 1; // 검색 범위를 뒷쪽 절반으로 좁힘
else
pr = pc - 1; // 검색 범위를 앞쪽 절반으로 좁힘
}while(pl <= pr);
return -1; // 검색 실패
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("요소수 : ");
int num = sc.nextInt();
int[] x = new int[num]; // 요소수가 num인 배열
System.out.println("오름차순으로 입력하세요.");
System.out.print("x[0]: "); // 첫 요소 입력받음
x[0] = sc.nextInt();
for(int i = 1; i < num; i++) {
do {
System.out.print("x[" + i + "]: ");
x[i] = sc.nextInt();
}while(x[i] < x[i - 1]); // 바로 앞의 요소보다 작으면 다시 입력받
}
System.out.print("검색할 값 : ");
int key = sc.nextInt();
int idx = binSearch(x, num, key);
if(idx == -1)
System.out.println("그 값의 요소가 없습니다.");
else
System.out.println("그 값은 x[" + idx + "]에 있습니다.");
}
}
시간 복잡도 구하기
선형 검색
O(f(n)) + O(g(n)) = O(max(f(n), g(n)))
※ max(a, b)는 a와 b 가운데 큰 쪽을 나타내는 메서드
int i = 0; // 1
while(i < n) { // 2
if(a[i] == key) // 3
return i; // 검색 성공(인덱스를 반환) // 4
i++; // 5
}
return -1; // 6즉 선형 검색은 O(1) + O(n) + O(n) + O(1) + O(n) + O(1) = O(max(1, n, n, 1, n, 1)) = O(n)이다.
이진 검색
static int binSearch(int [] a, int n, int key) {
int pl = 0; // 1
int pr = n - 1; // 2
do {
int pc = (pl + pr) / 2; // 3
if(a[pc] == key) // 4
return pc; // 5
else if(a[pc] < key) // 6
pl = pc + 1; // 7
else
pr = pc - 1; // 8
}while(pl <= pr); // 9
return -1; // 10
}이진 검색은 O(1) + O(1) + O(log n) + O(log n) + O(1) + O(log n) + O( log n ) + O( log n ) + O(log n) + O(1) = O(log n)이다.
자바는 배열에서 이진 검색을 하는 메서드를 표준 라이브러리로 제공한다.
java.util.Arrays 클래스의 binarySearch 메서드가 이진 검색이다.
binarySearch 장점
- 이진 검색 메서드를 직접 작성할 필요가 없다.
- 배열 요소의 자료형과 관계 없이 검색할 수 있다.
API 문서란?
- 라이브러리를 작성한 쪽에서 사용하는 방법을 적어 놓은 것이다.
binarySearch를 사용해서 검색을 성공한 경우
key와 일치하는 요소의 인덱스를 반환. 만약 일치하는 요소가 여러 개 있을 경우 어느 요소의 인덱스를 반환하는지 정해져 있지 않아 맨 앞에 요소의 인덱스를 반환한다는 보증이 없다.
binarySearch를 사용해서 검색을 실패한 경우
'배열 안에 eky가 있어야할 위치(삽입 포인트)를 추정할 수 있는 값'을 반환한다.
반환 값 : -x - 1