◼ 선형 검색
배열 하나가 있다.
{ 3 , 2 , 5 , 6 , 8 }
배열에서 숫자 6을 찾아보자.
인덱스 0부터 차례대로 배열을 살펴볼 것이다.
인덱스 0에는 값 3이 있으니 다음 인덱스 검색.
인덱스 1에는 값 2가 있으니 다음 인덱스 검색.
인덱스 2에는 값 5가 있으니 다음 인덱스 검색.
인덱스 3에 값 6을 찾았다.
이처럼 선형 검색은 어떤 배열이 있을 때, 이 배열의 인덱스 0부터 찾고자 하는 값이 나올 때까지 찾는 것을 선형 검색이라고 한다.
빅 오로 나타내면 O(N)으로 나타낼 수 있다. 최악의 케이스를 생각 했을 때 만약 6이 배열 맨 끝에 있다면 원소의 개수만큼 배열을 뒤져봐야하기 때문이다.
따라서 배열의 원소가 N이라면 N단계가 걸리므로 O(N)으로 나타낸다.
배열과 선형 검색은 가장 기본이 되는 자료구조와 알고리즘이라고 생각한다.
◼ 이진 검색
선형 검색은 배열의 원소가 8개이면 8단계가 걸리고, 그 두배인 16개이면 16단계가 걸린다.
만약 배열의 원소가 두 배로 늘어날 때마다 단계 수도 똑같이 두배로 늘어나는 선형검색과 달리 단지 한 단계만 더 걸리게 되는 검색 알고리즘이 있다면 효율성이 무척 증가할 것이다.
이를 이진 검색이라고 한다. 이진 검색을 살펴보자.
{ ? , ? , ? , ? , ? , ? , ? , ? , ?}
정렬된 배열에서 값 7을 찾는다고 하자.
이진 검색은 다음과 같이 동작한다.
- 1단계 : 가운데 셀부터 검색을 시작한다. 배열의 길이를 2로 나누어 가운데 셀의 인덱스의 값을 확인한다.
결과 : { ? , ? , ? , ? , 9 , x , x , x , x }
값이 9로 드러났으므로 7은 왼쪽 어딘가에 있다고 판단할 수 있다. 배열에 있는 셀의 절반을 제거한다.
- 2단계 : 9보다 왼쪽에 있는 셀들 중 가운데 값을 확인한다. 가운데 값이 두 개이니 임의로 왼쪽 값을 선택한다.
결과 : { X , 4 , ? , ? , X , X , X , X , X }
셀의 값은 4다. 따라서 7은 오른쪽 어딘가에 있어야 한다. 4와 그 왼쪽 값을 제거한다.
- 3단계 : 7일 수 있는 셀이 두개 남았다. 임의로 왼쪽 셀을 선택한다.
결과 : { X , X , 6 , ? , X , X , X , X , X }
- 4단계 : 마지막 남은 셀을 확인한다 (여기에 7이 없다면 배열에 7이 없다는 뜻이다)
결과 : { X , X , X , 7 , X , X , X , X , X }
4단계 만에 7을 찾았다.
배열의 원소의 개수는 9개이다.
선형검색에는 최악의 시나리오에서 9단계가 걸린다. 하지만 이진 검색은 4단계가 걸렸다.
지금은 별 차이가 없어보이지만 원소의 개수가 무척 많다고 가정해보자.
그 효율성 차이는 빅 오 표기법 게시물에서 볼 수 있다.
다음은 자바로 직접 구현해본 이진 검색이다.
public class BinarySearch {
public static int binarySearch( int[] arr, int searchValue ){
// 먼저 찾으려는 값이 있을 수 있는 상한선과 하한선을 정한다.
// 최초의 상한선은 배열의 첫 번째 값, 하한선은 마지막 값이다.
int lowerBound = 0;
int upperBound = arr.length-1;
// 상한선과 하한선 사이의 가운데 값을 계속해서 확인하는 루프를 시작한다.
while( lowerBound <= upperBound ){
// 상한선과 하한선 사이에 중간 지점을 찾는다.
int midpoint = (upperBound + lowerBound) / 2;
// 중간 지점의 값을 확인한다.
int valueAtMidPoint = arr[midpoint];
// 중간 지점의 값이 찾고 있던 값이면 검색을 끝낸다.
// 그렇지 않으면 더 클지 작을지 추측한 바에 따라 상한선이나 하한선을 바꾼다.
if( searchValue == valueAtMidPoint )
return midpoint;
else if( valueAtMidPoint > searchValue )
upperBound = midpoint - 1;
else if( searchValue > valueAtMidPoint )
lowerBound = midpoint + 1;
}
return -1;
}
}◼ 이진 검색은 항상 좋을까?
이진 검색은 빅 오로 나타내면 O(logN)이다. 이는 매우 효율적인 알고리즘이다.
하지만 이진 검색에는 단점이 있다. 바로 자료구조가 정렬된 배열이어야 한다는 것이다.
배열이 정렬 되어 있지 않다면 원소가 뒤죽박죽이므로 중간 값을 알 수 없다.
그렇다면 이것을 고려해야 한다.
전형적인 배열이라면 삽입은 맨 끝에 넣으면 되니 한 단계만 걸린다. 그러나 정렬된 배열은 순서를 지켜야하므로 값들을 먼저 대조한 후 , 삽입을 실행한다. 그리고 삽입을 위해 원소들을 오른쪽으로 한차례씩 옮겨주기까지 해야한다.
이진 검색은 확실히 강력한 알고리즘이다.
하지만 만약 프로그램의 주요 기능이 배열의 검색이 아닌 삽입이라면 배열의 정렬을 유지하는 것은 오히려 손해일 수 있다.
