선형검색(순차검색)이란?
요소가 직선형태로 나열된 배열에서 검색하고자 하는 값을 찾을 때까지 맨 앞 요소부터
순차적으로 검색하는 알고리즘
검색 종료 조건?
① 순차적으로 검색하는 중 원하는 값 찾기 성공! (n회 검색)
-> 배열 안에 값이 동일한 요소들이 있더라도 가장 먼저 값을 찾으면 검색 종료!
② 마지막 요소까지 검색해도 찾지 못했을 경우 실패!(n+1회 검색)
* 요소 하나씩을 검색할 때마다 위 종료조건 2개를 판단해야한다. (=조건판단에 의한 비용발생)
사용 조건?
요소(데이터)가 정렬되어 있지 않은 상태로 저장된 배열에서 원하는 요소(값)을 찾고자 할 때
사용할 수 있는 유일한 방법이다.
코드 ?
public class SeqSearch {
static int seqSearch(int[] a, int n , int key){
/* while문으로
int i = 0;
while (true){
if(i == n) return -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 stdIn = new Scanner(System.in);
System.out.println("요소수 : ");
int num = stdIn.nextInt();
int[] x = new int[num];
//요수수만큼 원하는 정수 값을 저장
for(int i = 0 ; i < x.length ; i++){
System.out.println("x[" + i + "] : " );
x[i] = stdIn.nextInt();
}
System.out.println("검색할 값 : ");
int key = stdIn.nextInt();
int idx = seqSearch(x,num,key);
if(idx == -1)
System.out.println("그 값의 요소가 없습니다.");
else
System.out.println("그 값은 x["+ idx +"]에 있습니다.");
}
}보초법을 통한 선형검색 구현
기존 선형 알고리즘에서는 종료조건을 위한 2번의 조건판단(찾고자 하는 값인가 ? , 마지막 요소였는가?)
이 필요했으며, 이에 따른 비용이 발생했다. 이러한 비용을 50%로 줄이는 방법이 보초법이다.
기존에 요소수에 따른 배열 크기 + 1인 배열을 생성하고 마지막 인덱스를 보초로 사용하여 찾고자하는 값을 저장한다.
이렇게 보초에 원하는 값을 저장해두면 마지막 인덱스까지 검색 시 원하는 값을 찾지 못하는 일은 발생하지 않을 것이다.
코드 ?
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 stdIn = new Scanner(System.in);
System.out.print("요소수 : ");
int num = stdIn.nextInt();
int x[] = new int[num+1]; // 보초로 사용하기 위한 크기(저장위치) 1개를 추가
for(int i = 0 ; i < num ; i++){
System.out.print("x["+i+"] :");
x[i] = stdIn.nextInt();
}
System.out.print("찾을 값 : ");
int key = stdIn.nextInt();
int idx = seqSearchSen(x,num,key);
}위 코드에서 볼 수 있듯이 원하는 값을 찾기 위해 순차적으로 반복문을 수행할 경우
조건식 1개만 판단한다 -> 비용이 기존에 절반으로 줄어든다.
return 시 찾은 요소가 보초에서 찾은 것인지를 판단하기 위한 조건식이 1개 증가