* 1) 선형검색의 한계 선형검색은 무한루프를 통해 검사를 진행하므로 종료조건에 있어 비용이 든다.
* 검색 실패, 검색 실패, 검색실패, 검색 성공 과 같은 식이다.
* => 이 비용을 반으로 줄이는 방법이 보초법이다.
* 1) 2를 검색해서 성공하는 조건 2 5 3 4 [2]
* 2) 5를 검색해서 실패하는 조건 0 2 4 1 [5]
* 이와 같이 끝자리 수에 검색하고자 하는 값을 보초라고하는데, 원하는 값이 존재하지 않아도 보초값까지 검색하면 종료가 성립된다.
* 다시 말해
* #선형 검색 의 경우 :
* int i = 0 으로 요솟수를 정의하고
* while(true) {
* if(i==n)
* return -1;
* if(a[i] == key)
* return 1;
* 과같이 첫번째 if문처럼 종료조건1을 달아야하는데, 이 과정이 필요가 없어지는 것이다.
* 따라서 보초는 반복문에서 종료 판단횟수를 2회에서 1회로 줄이는 역할을 한다.
package chapter1;
import java.util.Scanner;
public class SeqSearchSen {
// 요솟수가 n인 배열 a에서 key와 같은 요소를 보초법으로 선형 검색.
static int seqSearchSen(int[] a, int n, int key) {
int i = 0;
a[n] = key; // 보초를 추가 (a[요솟수] 니까 끝자리에 , 검색값을 한번 더 배치시킨다. 이것은 보초값을 가장 끝자리에 자리시키는 행위
while (true) {
if (a[i] == key) // 검색 성공!
break;
i++;
}
/*
for(i=0; i<n; i++) {
if(a[i] == key)
break;
}*/
// while이 반복되면, 찾은 값이 배열의 원래 데이터인지 아니면 보초인지 판단해야 한다.
// 변수 i 값이 n 이면 찾은 값이 보초값이므로 검색실패를 나타내는 -1을 반환한다.
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(ky+"은(는) x[" + idx + "]에 있습니다.");
}
}'1. 코딩테스트' 카테고리의 다른 글
| [자료구조와 알고리즘] 2. 이진검색 (0) | 2022.02.16 |
|---|---|
| [자료구조와 알고리즘] 1. 선형검색 (0) | 2022.02.16 |
