검색 알고리즘이란?
데이터 집합에서 원하는 값을 가진 요소를 찾아내는 알고리즘을 검색 알고리즘이라 한다.
검색 알고리즘은 데이터를 저장하는 자료구조에 영향을 많이 받는다.
ex) 배열, 선형 리스트, 이진 트리 등...
이번 게시글에서는 배열에서 검색을 하기위한 알고리즘을 사용하려 한다.
배열에서 검색하기 위한 알고리즘은 아래와 같다.
선형 검색 : 무작위로 늘어져 있는 데이터 집합에서 검색을 수행한다.
이진 검색 : 일정한 규칙으로 늘어져 있는 데이터 집합에서 빠른 검색을 수행한다.
해시법 : 추가, 삭제가 자주 일어나는 데이터 집합에서의 빠른 검색을 수행한다.
3가지 알고리즘 중 이번 게시글에선 선형 검색을 이용한 검색방법을 기록한다.
선형 검색이란?
선형 검색은 요소가 직선 모양으로 늘어선 배열에서 검색을 원하는 Key값을 가지는 요소를
만날때까지 맨 앞 요소부터 순차적으로 검색하는 방식을 선형 검색 또는 순차 검색이라고 한다.
선형 검색을 쉽게 이해하기 위해 이미지를 검색하여 첨부하였다.
선형 검색은 이미지와 같이 배열의 가장 앞 요소부터 검색할 Key가 있는 곳까지 순차적으로
검색하는 알고리즘이다.
그림에서 14를 찾기 위해 배열의 index 0부터 14 요소가 들어있는 index 4번까지 순차적으로 탐색한다.
하지만 만약 배열에 원하는 값이 없다면 어떻게 될까
성공과 실패 case가 2개가 생길것이다.
종료조건
검색 실패 : 종료 검색할 값을 찾지 못하고 배열의 끝까지 탐색한 경우
검색 성공 : 종료 검색할 값과 같은 요소를 발견한 경우
배열에서 선형 검색 해보기
주어진 배열과 검색할 key를 매개변수로 받고 검색할 key가 현재 배열의 어느 index에 있는지
반환하는 프로그램을 작성할 것이다. 주어진 배열과 key는 사용자 입력을 통해 받으려고 한다.
Main Method
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("요솟수 : "); // 배열의 길이를 의미
int num = sc.nextInt();
int[] x = new int[num] // 입력받은 길이만큼의 길이를 가진 배열을 생성
for(int i= 0; i < num; i++) { // 배열안에 요소들을 입력하자
System.out.print("x[" + i + "]: ");
x[i] = sc.nextInt();
}
System.out.print("검색할 값 : ");
int ky = sc.nextInt();
int idx = seqSearch(x, num, ky); // 배열 x에서 값이 key인 요소를 검색하는 메서드
if(idx == -1) { // 성공과 실패에 따른 분기
System.out.println("그 값의 요소가 없습니다.");
} else {
System.out.println("그 값은 x[" + idx + "]에 있습니다.");
}
}seqSearch
public int seqSearch(int[] x, int num, int key) {
int i = 0;
while(true) {
if(i == num) { // 끝까지 검색했을때도 찾지 못한경우
return -1;
}
if(x[i] == key) { // 찾은 경우 해당 index를 반환
return i;
}
i++;
}
}사용자의 입력을 통해서 배열을 생성하고, 그 배열 안에서 선형 검색으로 원하는 값을 찾는 프로그램을
간단히 작성하였다.
seqSearch 메서드에서 선형 검색을 이용한 검색을 사용하고 있는데 쉽게 설명하자면 다음과 같다.
- 매개변수로 배열, 배열의 길이, 검색할 값을 받는다
- 선형 검색을 위해 인덱스로 사용할 i 변수를 0으로 초기화한다.
- while문을 통해 무한 반복을 하고 조건에 따른 성공 유무를 확인하여 반환한다.
결과적으로 배열내 검색할 값이 있어 찾았다면 반복을 종료하고 해당 인덱스(i 변수)를 반환하고,
배열 끝까지 반복하면서 찾는 값이 없다면 임의의 값(-1)을 반환한다.
main method에서는 반환된 값을 가지고 성공 실패 유무 메세지를 출력한다.
보초법이란?
선형 검색은 반복할 때마다 종료조건 2개를 모두 판단한다.
이런 방식은 비용이 생각보다 커질 수 있다. 이러한 비용을 절반으로 줄이는 방법이 보초법이다.
무슨말인지 감이 안잡힐 수 있다. 보초법은 쉽게 말해서 배열의 마지막 인덱스에 검색할 key를 넣어두어 검색에 실패 하였더라도 종료 조건(검색할 값을 발견하였는가)만을 사용하여 조건을 1개만 판단하여,
검색에 소모되는 비용을 절반으로 줄일 수 있다.
말 그대로 검색할 값을 보초로 추가하여 배열을 끝까지 반복하면 무조건 검색 되기 때문에
조건을 1개만 사용할 수 있다. 위에서 작성한 seqSearch 메서드에 보초법을 추가해보자
보초법을 사용하여 선형 검색 해보기
seqSearch(보초법 추가)
public int seqSearch(int[] x, int num, int key) {
int i = 0;
x[num] = key; // 보초 추가
while(true) {
if(x[i] == key) { // 찾은 경우 반복을 멈춤
break;
}
i++;
}
return i == num ? -1 : i; // i와 num이 같은경우는 검색에 실패한 경우(보초를 찾은 경우)
}위와 같이 seqSearch 메서드를 수정했다 수정된 내용은 다음과 같다.
- 사용자로 부터 입력받은 배열의 길이라 5라면 배열 x의 길이는 0부터 4까지다.(원래대로라면)
(배열 x를 생성할때 입력받은 배열의 길이 +1을 해서 생성해야한다. 그럼 0부터 5까지이다.)- 보초는 사용자로 부터 입력받은 길이(5)를 인덱스로 사용하여 key를 보초로 추가한다.
- while문을 사용해 배열에 있는 요소와 검색할 key값이 같다면 반복을 멈추고 빠져나온다.
- 인덱스로 사용한 i와 num과 같은 경우는 보초를 탐색 성공한것이므로 -1을 반환하여 실패 처리한다. 외의 사항은 검색에 성공한것이므로 해당 인덱스를 반환한다.
이런식으로 보초법을 활용하면 실패, 성공을 판단하는 비용을 절반으로 줄여 선형 검색이 가능하다.
