1. 선형 검색
선형 검색(linear search)
- 요소가 직선 모양으로 늘어선 배열에서 검색은 원하는 키값을 갖는 요소를 만날 때까지 맨앞부터 순서대로 요소를 검색
- 선형 검색에서의 배열 검색의 종료 조건
1) 종료 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우 -> 검색 실패
2) 종료 검색할 값과 같은 요소를 발견한 경우 -> 검색 성공
- 배열의 요솟수가 n개 일때 종료 조건 1,2를 판단하는 횟수는 평균 n/2회
ex)
2를 검색
5를 검색
- 요솟수가 n인 배열 a에서 값이 key인 요소를 검색하는 코드
int i=0;
while(true) {
if(i==n)
return -1; //검색 실패(-1을 반환)
if(a[i] == key)
return i; //검색 성공(인덱스를 반환)
i++;
}
1) i==n이 성립하는 경우 (종료 조건 1)
2) a[i] == key가 성립하는 경우 (종료 조건 2)
- 메서드 seqSearch는 배열 a의 처음부터 끝까지 n개인 요소를 대상으로 값이 key인 요소를 선형 검색하고 검색한 요소의 인덱스를 반환
- 만약 값이 key인 요소가 여러 개 존재하면 검색 과정에서 처음 발견한 요소의 인덱스를 반환
- 값이 key인 요소가 존재하지 않으면 -1을 반환
import java.util.Scanner;
public 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 sc = new Scanner(System.in);
System.out.print("요솟수: ");
int num = sc.nextInt();
int[] x = new int[num]; //요솟수가 num인 배열
for(int i=0; i<num; i++) {
System.out.print("x["+i+"]:");
x[i] = sc.nextInt();
}
System.out.print("검색할 값: ");
int key = sc.nextInt();
int index = seqSearch(x,num,key); //배열 x에서 값이 key인 요소를 검색
if(index == -1)
System.out.println("그 값의 요소가 없습니다.");
else
System.out.println("그 값은 x["+index+"]에 있습니다.");
}
- 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을 반환)
}
...
2. 보초법으로 선형 검색 구현
보초법(sentinel method)
- 선형 검색에서 종료 조건 판단 비용을 반으로 줄이는 방법
ex)
2를 검색 (검색 성공)
5를 검색 (검색 실패)
- 맨 끝 요소 a[7]은 검색하기 전에 값을 저장하는 보초(sentinel)
- 보초에는 검색하고자 하는 키값을 저장
1) 2를 검색하기 위해 보초로 a[7]에 2를 저장
2) 5를 검색하기 위해 보초로 a[7]에 5를 저장
- 2)처럼 원하는 값이 원래 데이터에 존재하지 않아도 보초인 a[7]까지 '검색할 값과 같은 요소를 발견했는가'가 성립
- 원하는 키 값을 찾지 못했을 때를 판단하는 종료 조건 1) 이 없어도 됨
- 보초는 반복문에서 종료 판단 횟수를 2회에서 1회로 줄이는 역할을 함
//선형 검색(보초법)
import java.util.Scanner;
public class SeqSearchSen {
static int seqSearchSen(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 sc = new Scanner(System.in);
System.out.print("요솟수: ");
int num = sc.nextInt();
int[] x = new int[num+1]; //요솟수가 num+1인 배열
for(int i=0; i<num; i++) {
System.out.print("x["+i+"]:");
x[i] = sc.nextInt();
}
System.out.print("검색할 값: ");
int key = sc.nextInt();
int index = seqSearchSen(x,num,key); //배열 x에서 값이 key인 요소를 검색
if(index == -1)
System.out.println("그 값의 요소가 없습니다.");
else
System.out.println("그 값은 x["+index+"]에 있습니다.");
}
}
- while문에 의한 반복이 완료되면 찾은 값이 배열의 원래 데이터인지 아니면 보초인지 판단해야 함
- 변수 i값이 n이면 찾은 값이 보초이므로 검색 실패임을 나타내는 -1을 반환
- 변수 i값이 n이 아니면 찾은 값이 원래 데이터이므로 i값을 반환
