검색 알고리즘 - 선형 검색, 이진 검색

검색 알고리즘이란 데이터 집합에서 원하는 값을 가진 요소를 찾아내는 알고리즘이다.

알고리즘에 들어가기 앞서, 복잡도에 대해 알아보자.

 

복잡도

알고리즘의 성능을 객관적으로 평가하는 기준을 복잡도(complexity)라고 한다.

• 시간 복잡도(time complexity): 실행에 필요한 시간을 평가한 것
• 공간 복잡도(space complexity): 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것

 

선형 검색(linear search)

---

요소가 직선 모양으로 늘어선 배열에서의 검색은 원하는 키 값을 갖는 요소를 만날  때까지 맨앞부터 순서대로 요소를 검색하면 되는데, 이것이 선형 검색(linear search) 또는 순차 검색(sequential search)이라는 알고리즘이다.

[검색이 종료되는 종료 조건]
1. 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우
2. 검색할 값과 같은 요소를 발견한 경우

  선형 검색으로 배열에서 33 찾기

코드구현 - JavaScript

function linearSearch(arr, n, key){ //배열, 배열 요소수, 찾는 값
	
    let i = 0;
    
    while(true){
    if(i === n) return -1; //검색 실패(-1을 반환)
    if(arr[i] === key) return i; //검색 성공!(인덱스를 반환)
    i++;
    
}

배열의 요솟수가 n개일 때 조건 1, 2를 판단하는 횟수는 평균 n/2 회이다.

 

보초법

선형 검색은 반복할 때마다 위의 종료조건 1과 2를 모두 반복한다.

이 비용을 반으로 줄이는 방법이 보초법(sentinel method)이다. 검색하고자 하는 key 값을 배열의 맨끝 요소에 저장한다. 이 때 저장하는 값을 보초라고 한다. 

보초법을 실행할 경우 위의 종료 조건 중 2번만 만족시키면 되기 때문에 반복 종료에 대한 판단 횟수는 실제로 절반으로 줄어들게 된다. 

 

코드구현 - JavaScript

function seqSearchSen(arr, n, key) {
	
    arr[n] = key; //마지막에 보초를 추가
    
    let i = 0;
    
    while(true){
    	if(arr[i] == key) break;
        i++;
    }
    
    return i == n? -1 : i; //i가 n이면 i값은 보초이므로 -1을 반환한다.
}

하지만 컴퓨터에게는 N번 걸리는 횟수나 N/2번 걸리는 횟수나 거의 차이가 없다.

 

선형 검색은 n에 비례하는 횟수만큼 검색을 실행하기 때문에 복잡도를 O(n)으로 표기한다.

 

이진 검색(binary search)

---

이진 검색은 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘이다. 

이진 검색을 적용하는 전제 조건은 데이터가 키 값으로 이미 정렬되어 있다는 것이다. 이진 검색은 선형 검색보다 좀 더 빠르게 검색할 수 있다는 장점이 있다.

 

어떤 배열 A가 오름차순으로 정렬되어있다고 하자.

배열 A의 중심값을 기준으로 잡는다. 위에서도 언급했지만, 이는 배열이 이미 정렬되었다는 가정하에 가능한 것이다.

그리고나서 찾고자하는 key 값이 중심값보다 작을 경우, 인덱스 0부터 중심값의 index-1까지의 범위를 변경한 후, 이 범위의 중심값과 비교한다.

만약 key값이 중심값보다 클 경우, 중심값의 index+1부터 마지막 index의 범위로 옮겨가서 이 범위의 중심값과 비교한다.

이 과정을 반복하면서 점점 범위를 좁혀나가다가, 검색할 범위가 더이상 없거나 찾고자하는 key값을 찾을 경우 검색을 종료한다.

이진 검색으로 배열에서 47 찾기

 

이를 코드로 구현하면 아래와 같다.

 

검색범위의 맨 앞 인덱스는 left,

검색범위의 맨 뒤 인덱스는 right = arr.length - 1 (배열의 길이 - 1),

검색범위의 중앙 인덱스는 mid = (arr.length - 1) / 2 로 초기화한다.

 

여기서 주목할 점을 이진 검색을 한 단계씩 진행할 때마다 검색 범위가 (거의) 반으로 좁혀진다는 것이다. 선형 검색과 비교해보해보면, 선형 검색은 검사한 요소를 하나씩 제외시키는 반면, 이진 검색은 검색할 요소가 해당단계에서 다음단계의 검색할 범위의 중간 지점으로 단숨에 이동한다는 것이다.

 

이진 검색 알고리즘의 종료 조건은 아래 조건 중 하나만 성립하면 된다.

[검색이 종료되는 종료조건]
1. arr[mid]와 key값이 일치하는 경우
2. 검색범위가 더이상 없는 경우

 

코드구현 - JavaScript

function binarySearch(arr, key) {
    let left = 0;
    let right = arr.length - 1;
    
    while (left <= right) {
        const mid = (arr.length-1)/2;
        if (arr[mid] === key) {
            return mid;
        }
        if (arr[mid] < key) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

 

이진 검색은 검색을 반복할 때마다 검색 범위가 절반이 되므로 검색에 필요한 비교 횟수의 평균 값은 log n이다. 검색에 실패한 경우는 [log(n + 1)]회, 검색에 성공한 경우는 대략 log n - 1회이다. 따라서 이진 검색 알고리즘의 복잡도는 O(log n)이다.