※ 순차 검색(Sequential Search)
- 일렬로 되어있는 자료를 처음부터 마지막까지 검색하는 방법
- 선형 검색(Linear Search)이라고도 한다.
- 검색하는 양에 따라 효율이 달라진다. 자료의 양이 많아질수록 비효율 적이지만 알고리즘이 단순하여 구현이 쉽다.
※ 정렬되지 않은 순차 자료구조에서의 순차 검색
- 첫 번째 원소부터 시작하여 키값이 일치하는 원소를 찾는다.
- 정렬이 되어있지 않기때문에 키값이 일치하는 원소를 찾을때 까지 검색한다.
- 끝까지 검색했는데 키값이 없다면 검색 실패
※ 정렬이 된 순차 자료구조에서의 순차 검색
- 첫 번째 원소부터 시작하여 키값이 일치하는 원소를 찾는다.
- 단 정렬되어 있기 때문에 키값보다 작거나 같은 원소까지만 검색을 하고 그 이후는 하지 않는다.
- 키값보다 큰 원소 직전까지 검색을 했는데 키값이 없다면 검색 실패
Sequential Search
public class SequentialSearch {
public void sequentialSearch1(int[] a, int size, int key){
int idx =0;
for(int i=idx; i<size; i++){
if(a[i] == key){
System.out.println((i+1) + "번째 원소에서 검색 완료");
return;
}
idx++;
}
System.out.println((idx+1) + "번째 원소에서 검색 실패");
}
public void sequentialSearch2(int[] a, int size, int key){
for(int i=0; i<size; i++){
if(a[i] > key){
System.out.println((i+1)+"번째 원소에서 검색 실패");
return;
}
if(a[i] == key){
System.out.println((i+1) + "번째 원소에서 검색 완료");
return;
}
}
}
}
Main
public class Main {
public static void main(String[] args) {
int a1[] = {8,30,1,9,11,19,2};
int size = a1.length;
SequentialSearch ss = new SequentialSearch();
System.out.println("\n정렬되지 않은 자료에서 순차검색");
ss.sequentialSearch1(a1, size, 9);
ss.sequentialSearch1(a1, size, 6);
int a2[] ={1,2,8,9,11,19,29};
size = a2.length;
System.out.println("\n정렬되어 있는 자료에서 순차검색");
ss.sequentialSearch2(a2, size, 9);
ss.sequentialSearch2(a2, size, 6);
}
}
※ 색인 순차 검색(Index Sequential Search)
- 인덱스 테이블을 추가로 사용하여 탐색의 효율을 높인 검색 방법이다.
- 인덱스 테이블은 index와 key값으로 2차원 배열이며 일정간격의 인덱스와 키값을 저장해 둔것이다.
- 그래서 어떤 키값이 들어왔을때 IndexTablekey[i] <= key < indexTableKey[i+1] 일때 배열의 검색범위는 indexTableKey값이 가르키는 두 인덱스 사이만 검색하면 된다.
- 인덱스 테이블이 크기가 너무 크면 검색할때 배열에서 검색하는 범위는 작아지지만 인덱스 테이블의 검색 범위가 커진다.
- 인덱스 테이블의 크기를 줄이기 위해 인덱스 사이의 범위를 크게하면 검색해야하는 범위도 넓어지기 때문에 인덱스 테이블을 검색하는 범위는 작아지지만 배열에서 검색 범위가 커진다.
IndexSequentialSearch
public class IndexSequentialSearch {
int idxTable[][] = null;
public IndexSequentialSearch(int a[]) {
// TODO Auto-generated constructor stub
makeIdxTable(a);
}
public void IndexSequentialSearch(int[] a, int size, int key){
for(int i=0; i<idxTable.length; i++){
if(i+1 <= idxTable.length-1 ){
if(idxTable[i][1] <= key && key < idxTable[i+1][1]){
sequentialSearch(a, idxTable[i][0]
, idxTable[i+1][0],key);
break;
}
}else{
sequentialSearch(a,idxTable[idxTable.length-1][0]
, a.length-1, key);
break;
}
}
}
public void sequentialSearch(int[]a, int stIdx, int edIdx, int key){
for(int i=stIdx; i<=edIdx ; i++){
if(a[i] == key){
System.out.println((stIdx+1) + "~" + (edIdx+1)
+ "사이의 " + (i+1) + "번째 원소에서 검색 완료");
return;
}
}
System.out.println((stIdx+1) + "~" + (edIdx+1) + "사이에 검색값 "
+ key + "없음.");
}
public void makeIdxTable(int[] a){
int tableSize = (a.length)/3;
int aIdx =0;
int idxInterval = (a.length)/tableSize;
idxTable = new int[tableSize][2];
for(int i=0; i<idxTable.length; i++){
idxTable[i][0] = aIdx;
System.out.print(idxTable[i][0] + ", ");
idxTable[i][1] = a[aIdx];
System.out.println(idxTable[i][1]);
aIdx += idxInterval;
}
System.out.println("인덱스 테이블 생성 완료");
}
}
Main
public static void main(String[] args) {
int a[] = {1,2,8,9,11,19,29,30,40,100};
int size = a.length;
IndexSequentialSearch iss = new IndexSequentialSearch(a);
System.out.println("\n 색인순차검색");
iss.IndexSequentialSearch(a, size, 9);
iss.IndexSequentialSearch(a, size, 6);
iss.IndexSequentialSearch(a, size, 100);
}
'플밍 is 뭔들 > 자료구조' 카테고리의 다른 글
| 08-3 이진 트리 검색 (0) | 2016.12.04 |
|---|---|
| 08-2 이진 검색 (0) | 2016.12.04 |
| 07-9 트리 정렬 (0) | 2016.11.30 |
| 07-8 힙 정렬 (0) | 2016.11.30 |
| 07-7 기수 정렬 (0) | 2016.11.30 |
