[Do it!] 3장. 검색 (Search)

 

검색 (=탐색)

데이터 집합에서 원하는 값을 가진 요소를 찾아내는 작업

 

 

검색 기법

1. 배열 검색

2를 검색

 

2. 선형 리스트 검색

53을 검색

 

3. 이진검색트리 검색

4를 검색

 

 

 

배열 검색에서 사용되는 알고리즘

1. 선형 검색, Linear Search (=순차 검색, Sequential Search)

  -  무작위로 늘어놓은 데이터 모임에서 검색을 수행

function linearSearch(arr, key){
    for(let i = 0; i < arr.length; i++){
        if(arr[i] === key){
            return i; //검색 성공
        }
    }
    return -1; //검색 실패
}

 

※ 보초법

기존의 선형 검색에서는 반복문의 종료 조건이 2가지다.

    1. 검색할 값을 발견하지 못하고 배열의 끝에 도달한 경우

    2. 검색할 값과 같은 요소를 발견한 경우

 

반복될 때마다 종료 조건을 검사하는 비용을 반으로 줄이기 위해 사용할 수 있는 방법이 보초법이다. 

 

2를 검색 (검색 성공)

5를 검색 (검색 실패)

위 그림에서와 같이 보초법은 검색하고자 하는 key값을 원래 데이터 배열 끝에 추가한다. 

이때 저장하는 값을 보초(sentinel)라고 부른다.

이렇게 하면 원래의 데이터에 찾고자 하는 값이 없더라도 결국 보초로 인해 종료 조건 2를 만족하기 때문에

원하는 값을 찾지 못했을 때를 판단하는 종료 조건 1은 없어도 된다. 

 

function linearSearch(arr, key){
	var i = 0;
    var n = arr.length;
    arr.push(key); // 보초 추가
    
    while(true) {
        if(arr[i] === key){
            break; //검색 성공
        }
        i++;
    }
    return i === n ? -1 : i; // 찾은 값이 보초인지 원래 데이터인지 판단
}

 

 

 

2. 이진 검색, Binary Search

  -  일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색을 수행

  -  데이터가 오름차순 혹은 내림차순으로 정렬(sort)되어 있는 것이 전제 조건

 

이진 검색 예시 (39를 검색) - 검색 성공

 

    1) arr[pc] < key일 때

       데이터가 이미 오름차순으로 정렬되어 있기 때문에

       arr[pl] ~ arr[pc]는 key보다 작은 것이 분명하므로 검색 대상에서 제외

       pl = pc + 1로 값을 변경해 검색 범위를 좁힘

 

    2) arr[pc] > key일 때

       arr[pc] ~ arr[pr]은 key보다 큰 것이 분명하므로 검색 대상에서 제외

       pr = pc - 1로 값을 변경해 검색 범위를 좁힘

 

 

이진 검색 알고리즘의 종료 조건

    1. arr[pc]와 key가 일치하는 경우, arr[pc] === key

    2. 검색 범위가 더 이상 없는 경우, pl > pr

 

이진 검색 예시 (6을 검색) - 검색 실패

 

이진 검색은 검색을 반복할 때마다 검색 범위가 절반이 되므로 검색에 필요한 비교 횟수의 평균값은 log n 이다.

검색에 실패한 경우는 ⌈log (n+1)⌉ 회, 검색에 성공한 경우는 대략 log n - 1 회다.

※ 천장(올림) 메서드: ⌈x⌉는 x보다 크거나 같으면서 가장 작은 정수

 

 

• 반복문을 사용하여 작성한 코드

function binarySearch(arr, key){
    var pl = 0;				// 검색 범위 첫 인덱스
    var pr = arr.length - 1;		// 검색 범위 끝 인덱스
 	
    do {
    	var pc = (pl + pr) / 2;	// 중앙 요소의 인덱스
        
        if (arr[pc] === key) 
        	return pc;		// 검색 성공
        else if (arr[pc] < key)
        	pl = pc + 1;		// 검색 범위를 우측 절반으로 줄임
        else 
        	pr = pc - 1;		// 검색 범위를 좌측 절반으로 줄임
    } while (pl <= pr);
    
    return -1;				// 검색 실패
}

 

• 재귀호출을 사용하여 작성한 코드 

function binarySearch(arr, key, pl, pr){
    if (pl > pr) return -1;
    var pc = Math.ceil((pl + pr) / 2);
    
    if (arr[pc] === key) 
    	return pc;
    else if (arr[pc] > key)
    	pl = pc + 1;
    else 
    	pr = pc - 1;
        
    return binarySearch(arr, key, pl, pr);
}

 

 

 

3. 해시법

  -  추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행합니다. 

  -  체인법: 같은 해시 값의 데이터를 선형 리스트로 연결하는 방법

  -  오픈 주소법: 데이터를 위한 해시 값이 충돌할 때 재해시하는 방법

 

 

 

 

복잡도 (Complexity)

알고리즘의 성능을 객관적으로 평가하는 기준

    1. 시간 복잡도(Time Complexity) : 실행에 필요한 시간을 평가한 것

    2. 공간 복잡도(Space Complexity) : 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것

 

 

선형 검색의 시간 복잡도

function linearSearch(arr, key){
    var i = 0; 				// 1회 - O(1)
    
    while(i < arr.length){		// n/2회 - O(n)
        if(arr[i] === key)		// n/2회 - O(n)
            return i; 			// 1회 - O(1)
        i++;					// n/2회 - O(n)
    }
    return -1; 				// 1회 - O(1)
}

 

※ 복잡도를 표기할 때 사용하는 O는 Order에서 따온 것으로, O(n)은 'O - n', 'Order n', 'n의 Order'라고 읽는다.

• O(n): n에 비례하는 횟수만큼 실행하는 경우의 복잡도
• O(1): n과 무관한 상수 횟수만큼 실행한는 경우의 복잡도
• 전체 복잡도는 차원이 가장 높은 복잡도를 선택
• 따라서 선형 검색 알고리즘의 복잡도는 O(n)

 

 

이진 검색의 시간 복잡도

function binarySearch(arr, key){
    var pl = 0;				// O(1)
    var pr = arr.length - 1;		// O(1)
 	
    do {
    	var pc = (pl + pr) / 2;	// O(log n)
        
        if (arr[pc] === key) 		// O(log n)
        	return pc;		// O(1)
        else if (arr[pc] < key)	// O(log n)
        	pl = pc + 1;		// O(log n)
        else 
        	pr = pc - 1;		// O(log n)
    } while (pl <= pr);		// O(log n)
    
    return -1;				// O(1)
}

 

• 이진 검색 알고리즘의 복잡도는 O(log n)

 

 

복잡도의 대소관계