검색기법 3가지
- 배열검색
- 선형 리스트 검색
- 이진검색트리 검색
배열 검색
- 선형검색 : 늘어놓은 데이터를 검색
- 이진검색 : 일정한 규칙으로 늘어놓은 데이터를 검색
- 해시법 : 추가, 삭제가 자주 일어나는 데이터를 검색
(체인법 : 같은 해시 값의 데이터를 선형 리스트로 연결하는 방법)
(오픈 주소법 : 데이터를 위한 해시 값이 충돌할 때 재해시 하는 방법)
선형 검색
요소가 직선 모양으로 늘어선 배열에서의 검색
- 키 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색
배열 검색의 종료 조건
1. 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우
2. 검색할 값과 같은 요소를 발견한 경우
package search;
import java.util.Scanner;
public class Ex01 {
static int seqSearch(int[] a, int n, int key) {
for(int i = 0; i < n; i ++)
if (a[i] == key)
return i;
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];
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);
if(idx == -1)
System.out.println("그 값의 요소가 없습니다.");
else
System.out.println(ky + "은(는) x[" + idx + "]에 있습니다.");
}
}
해당 메서드는 배열의 처음부터 끝까지 n개의 요소를 대상으로 값이 key인 요소를 선형 검색하고 검색한 요소의 인덱스를 반환합니다.
또한 값이 key인 요소가 여러 개 존재할 경우 반환값은 검색 과정에서 처음 발견한 요소의 인덱스가 됩니다.
값이 key인 요소가 존재하지 않으면 -1을 반환합니다.
보초법
- 종료 조건을 검사하는 비용을 반으로 줄이는 방법
- 검색하기 전 요솟수에 1을 더하여 맨 끝 요소에 검색하고자 하는 키 값을 저장합니다.
package search;
import java.util.Scanner;
public class Ex02 {
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 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 = seqSearch(x, num, ky);
if(idx == -1)
System.out.println("그 값의 요소가 없습니다.");
else
System.out.println(ky + "은(는) x[" + idx + "]에 있습니다.");
}
}
'프로그래밍 연구 > 알고리즘' 카테고리의 다른 글
[알고리즘 독학] 재귀 알고리즘(1) 재귀의 기본 (0) | 2022.04.11 |
---|---|
[알고리즘 독학] 큐(Queue) (0) | 2022.03.31 |
[알고리즘 독학] 스택(Stack) (0) | 2022.03.29 |
[알고리즘 독학] 검색 알고리즘 개념(2) (0) | 2022.03.28 |