검색 알고리즘 : 데이터 집합에서 원하는 값을 가진 요소를 찾아냄
검색은 대부분 데이터를 저장하는 방식인 자료구조에 많은 영향을 받는다.
'배열'에서 검색할 때는 다음 알고리즘을 활용한다.
- 선형 검색 : 무작위로 늘어서 있는 데이터 모임에서 검색을 수행한다.
- 이진 검색 : 일정한 규칙으로 늘어서 있는 데이터 모임에서 아주 빠른 검색을 수행한다.
- 해시법 : 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행한다.
- 체인법 : 같은 해시값의 데이터를 선형 리스트로 연결하는 방법
- 오픈 주소법 : 데이터를 위한 해시값이 충돌할 때 재해시하는 방법
1. 선형 검색
선형 검색은 배열에서 검색하는 방법 중 가장 기본적인 알고리즘이다.
정렬되지 않은 배열에서 검색할 때 사용하는 유일한 방법이다. (처음부터 쭉 다 찾는..)
요소가 직선모양으로 늘어선 배열에서 검색은 원하는 키값을 갖는 요소를 만날 때까지
맨 앞부터 순서대로 요소를 검색하게 된다.
원하는 요소를 찾았거나, 맨 마지막까지 찾지 못하면 검색은 종료된다.
위 경우 요소수가 n개일 때 종료 조건을 판단하는 횟수는 평균 n/2회이다.
요소수가 n개인 배열 a에서 값이 key인 요소를 검색하는 코드는 다음과 같다.
while문 사용
int i = 0;
while (true) {
if ( i == n )
return -1; // 검색실패 (-1을 반환)
if ( a[i] == key )
return i; // 검색성공 (인덱스를 반환)
i++
}for문 사용
static int seqSearch(int[] a, int n, int key) {
for (int i = 0; i < n; i++)
if (a[i] == key)
return i; // 검색 성공 (인덱스를 반환)
return -1; // 검색 실패 (-1을 반환)
}위 코드를 사용하여 만든 실습코드는 아래와 같다.
전체코드
package DataStructureBasic;
// 선형검색
import java.util.Scanner;
class SeqSearch {
//--- 요소수가 n인 배열 a에서 key와 값이 같은 요소를 선형 검색 ---//
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++;
}
}
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
System.out.print("요소수: ");
int num = stdIn.nextInt();
int[] x = new int[num]; // 요소수가 num인 배열
for (int i = 0; i < num; i++) {
System.out.print("x[" + i + "]: ");
x[i] = stdIn.nextInt();
}
System.out.print("검색할 값: "); // 키값을 입력받음
int ky = stdIn.nextInt();
int idx = seqSearch(x, num, ky); // 배열 x에서 값이 ky인 요소를 검색
if (idx == -1)
System.out.println("검색 값의 요소가 없습니다.");
else
System.out.println("검색 값은 x[" + idx + "]에 있습니다.");
}
}만약 값이 key인 요소가 여러 개 존재하면 검색 과정에서 처음 발견한 요소의 인덱스를 반환한다.
값이 key인 요소가 존재하지 않으면 -1을 반환한다.
선형 검색은 아래 조건 2가지를 만족해야 반복을 종료한다.
① 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우
② 검색할 값과 같은 요소를 발견한 경우
단순무식한 방법이기 때문에, 이러한 과정들이 쌓이면 검사하는 비용이 많아 진다.
이러한 비용을 50% 줄일 수 있는 방법이 '보초법'이다. (sentinel method)
Do it! 알고리즘 입문 - 자바편(103p)
검색하려는 값을 맨 끝 요소로 저장하는 방법이다.
위 그림의 b방법의 경우 원하는 값이 데이터에 존재하지 않아도,
'① 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우'
라는 방법이 필요없어지게 된다.
즉, '② 검색할 값과 같은 요소를 발견한 경우'만 사용하게 되어
종료 판단 횟수를 절반으로 줄일 수 있다.
보초법을 사용하여 코드를 수정하면 아래와 같다
전체코드(보초법 적용한 최종)
// 선형 검색(보초법)
package DataStructureBasic;
import java.util.Scanner;
class SeqSearchSen {
//--- 요소수가 n인 배열 a에서 key와 값이 같은 요소를 보초법으로 선형 검색 ---//
static int seqSearchSen(int[] a, int n, int key) {
int i = 0;
a[n] = key; // 보초를 추가
while (true) { // 종료조건이 1개로 줄어듬
if (a[i] == key) // 검색 성공
break;
i++;
}
return i == n ? -1 : i;
}
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
System.out.print("요소수 : ");
int num = stdIn.nextInt();
int[] x = new int[num + 1]; // 요소수가 num + 1인 배열
for (int i = 0; i < num; i++) {
System.out.print("x[" + i + "] : ");
x[i] = stdIn.nextInt();
}
System.out.print("검색 값 : "); // 키값을 읽력받음
int ky = stdIn.nextInt();
int idx = seqSearchSen(x, num, ky); // 배열 x에서 값이 ky인 요소를 검색
if (idx == -1)
System.out.println("검색 값의 요소가 없습니다.");
else
System.out.println("검색 값은 x[" + idx + "]에 있습니다.");
}
}- 검색할 값 key를 보초로 a[n]에 대입한다.
- 배열 요소를 순서대로 스캔한다. (보초법을 사용해 if문이 1개로 줄어듦)
- 반복문(while)이 완료되면 찾은 값이 배열의 원래 데이터인지 아니면 보초인지 판단해야한다.
변수 i값이 n이면 찾은 값이 보초이므로 검색 실패임을 나타내는 -1을 반환하고,
변수 i값이 n이 아니면 찾은 값이 원래 데이터이므로 i값을 반환한다.
2. 이진 검색
이 알고리즘을 적용하는 전제조건은 데이터가 키값으로 이미 정렬(sort)되어 있어야 한다는 것이다.
이진 검색은 선형 검색보다 좀 더 빠르게 검색할 수 있다는 장점이 있다.
검색을 반복할 때마다 범위가 절반이 되므로 검색에 필요한 비교 횟수의 평균값은 log n이다.
이진 검색은 배열요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘이다.
그림과 같이 오름차순으로 정렬된 데이터에서 '76'을 검색하는 과정을 생각해보자.
먼저 배열의 중앙에 위치한 요소인 47부터 검색을 시작한다.
그리고 검색할 값 76은 47보다 크므로 47보다 작은 배열값들은 모두 고려 대상이 아니게 된다.
다음으로 47보다 큰 뒤쪽 검색 범위의 중앙에 위치한 요소인 77을 선택한다.
77은 검색할 값 76보다 크므로 77을 포함한 뒤의 값 역시 고려 대상에서 제외시킨다.
그리고 남은 데이터들의 중앙값인 64를 선택하고 76과 비교하게 되면 검색이 끝이 난다.
이진 검색은 아래 조건 2가지를 만족해야 반복을 종료한다.
① 중앙값과 검색할 값이 일치할 경우(2개만 남은 경우 앞쪽이 중앙값)
② 검색 범위가 더 이상 없는 경우
전체코드
// 이진 검색
package DataStructureBasic;
import java.util.Scanner;
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 stdIn = new Scanner(System.in);
System.out.print("요소수: ");
int num = stdIn.nextInt();
int[] x = new int[num]; // 요소수가 num인 배열
System.out.println("오름차순으로 입력하세요.");
System.out.print("x[0]: "); // 첫 요소 입력받음
x[0] = stdIn.nextInt();
for (int i = 1; i < num; i++) {
do {
System.out.print("x[" + i + "]: ");
x[i] = stdIn.nextInt();
if(x[i] < x[i - 1])
System.out.println("더 큰 수를 입력하세요.");
} while (x[i] < x[i - 1]); // 바로 앞의 요소보다 작으면 다시 입력받음
}
System.out.print("검색할 값: "); // 키값을 읽어 들임
int ky = stdIn.nextInt();
int idx = binSearch(x, num, ky); // 배열 x에서 값이 ky인 요소를 검색
if (idx == -1)
System.out.println("검색 값의 요소가 없습니다.");
else
System.out.println("검색 값은 x[" + idx + "]에 있습니다.");
}
}