이번 장에서는 '검색 알고리즘'에 대해서 포스팅하려한다.
원래 알고 있는 개념이지만, 잘 사용하지 않은 방법들도 있어 포스팅하며 또 한번 상기하고,
기록을 해두려 한다.
이번 장에서는 검색 알고리즘에서도 배열, 선형, 이진 알고리즘에 대해 알아보자.검색 알고리즘이란?
- 선형 알고리즘 : 무작위로 늘어서 있는 데이터 모임에서 검색을 수행.
- 이진 검색 : 일정한 규칙으로 늘어서 있는 데이터 모임에서 아주 빠른 검색을 수행.
- 해시법 : 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행.
- 체인법 : 같은 해시값의 데이터를 선형 리스트로 연결하는 방법.
- 오픈 주소법 : 데이터를 위한 해시값이 충돌할 때 재해시하는 방법.
- 배열을 활용한 검색
- 장점 : 빠르다.
- 단점 : 데이터를 추가, 삭제할 경우 비용이 많이 든다.
선형 검색
- 요소가 직선 모양으로 늘어선 배열에서 검색은 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색.
- 검색 종료 조건
- 검색 성공 : 종료 검색할 값과 같은 요소를 발견한 경우.
- 검색 실패 : 종료 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우.
int i = 0;
while(true){
if (i==n) // 검색 실패
return -1;
if (a[i] == key) // 검색 성공
return i;
i++;
}-> 위 코드는 선형 검색을 while문으로 활용하여 구현한 코드이다.
이때, while문의 조건을 true로 두고 무한루프를 돌며 return을 받아 while루프를 탈출한다.
- for문 사용-
for(int i=0; i<n; i++){
if(a[i] == key)
return i;
return -1;
}보초법
처음 들어보는 용어다... (이런걸 한번 알아가보고자 하는 포스팅이다!)
보초법은 반복문에서 종료 판단 횟수를 2회에서 1회로 줄이는 역할을 한다.
그 방식을 코드를 통해 알아보자.
int i = 0;
a[n] = key; // 보초법을 위해 인데스 마지막에 키값을 추가.
while(true){
if (a[i] == key) // 검색 성공
break;
i++;
}
return i == n ? -1 : 1; // 보초법-> 위 코드는 기존 선형 검색에서 보초법을 추가하여 if 조건문을 2개에서 1개로 절감하는 코드이다.
기존 검색하는 배열 a의 크기가 n이라면 크기를 n+1까지 선언해준다.
다음 맨 마지막 인덱스에 key값을 추가해준다.
while loof에서는 검색 성공의 조건만이 존재한다.
이후 i값이 맨 마지막 인덱스 일 경우 검색 실패로 -1이 성공일 경우 1로 검색 성공이 된다.
이진 검색
요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘.
즉, 이진 검색의 조건은 배열이 정렬되어 있어야한다는 점이다.
- 배열의 맨 처음 인덱스 : pl (0)
- 배열의 맨 마지막 인덱스 : pr (n-1)
- 배열의 가운데 인덱스 : pc (n-1)/2
위 내용은 길이가 n인 배열에서 6(key)을 찾는 과정을 이진 검색으로 풀어가는 그림이다.
그림과 같이 pc가 key보다 작으므로 pc보다 큰 값에서 다시 검색을 시작한다.
이와 같은 방식을 반복하여 해방 key값을 배열에서 찾아낸다.
이는 정렬된 배열이기에 가능한 방식이다.
정리
- 중앙값 a[pc]가 key보다 작을 때 : 중앙 바로 왼쪽 인덱스를 새로운 검색 범위로의 pr로 하여 앞쪽으로 좁힌다.
- 중앙값 a[pc]가 key보다 클 때 : 중앙 바로 오른쪽 인덱스를 새로운 검색 범위로의 pr로 하여 뒤쪽으로 좁힌다.
- 이진 검색 종료 조건
- a[pc]와 key가 일치
- 검색 범위가 더 이상 없을 때
class BinSearch {
//--- 요솟수가 n개인 배열 a에서 key와 같은 요소를 이진 검색 ---//
static int binSearch(int[] a, int n, int key) {
int pl = 0; // 검색 범위의 첫 인덱스
int pr = n - 1; // 검색 범위의 끝 인덱스
do {
int pc = (pl + pr) / 2; // 중앙 요소 인덱스
if (a[pc] == key)
return pc; // 검색 성공!
else if (a[pc] < key)
pl = pc + 1; // 검색 범위를 뒤쪽 절반으로 좁힘
else
pr = pc - 1; // 검색 범위를 앞쪽 절반으로 좁힘
} while (pl <= pr);
return -1; // 검색 실패
}
}위 코드는 이진 검색에 코드이다.
do에서 if문을 통해 비교 연산으로 범위를 좁혀나가는 것을 볼 수 있다.
Arrays.binarySearch에 의한 이진 검색
- 장점
- 이진 검색 메서드를 직접 작성할 필요가 없다.
- 배열 요소의 자료형과 관계없이 저장할 수 있다.
- 검색 결과
- 검색 성공 : key와 일치하는 요소의 인덱스 반환
- 검색 실패 : 배열 안에 key가 있어야 할 위치를 추정할 수 있는 값을 반환
생각하는 개발자가 되겠습니다!!