알고리즘 - 이진 탐색

 

 

탐색은 배열 형태로 주어진 데이터에서 원하는 값을 가진 데이터를 찾는 알고리즘이다.

이진 탐색은 입력된 데이터가 정렬된 상태로 주어진 경우에 효과적으로 수행할 수 있다. 여기서는 데이터가 오름차순으로 정렬되어 있다고 가정한다.

 

먼저 큰 틀에서 심플하게 4단계로 생각해보았다.

1. 배열은 오름차순 기준이고, 탐색키 key 와 가운데 원소 값이 같다면 즉시 종료한다.
2. 가운데 원소를 기준으로 좌우로 배열을 쪼갠다.
3. key 와 가운데 원소를 비교해서 작으면 좌배열 크면 우배열에서 검사를 다시 시작한다.
4. key 를 찾을 때까지 1번부터 다시 반복한다.

 

재귀적 용법을 사용한 이진트리 알고리즘

BinarySearch 라는 함수의 입력값은 arr과 right,left, key 라는 값이다.

arr 은 오름차순 정렬된 배열이다.

key 는 A 배열에서 찾을 값(탐색키)이다.

left는 배열의 첫번째 인덱스, right 은 배열의 마지막 인덱스를 의미한다. (탐색 구간의 정의)

// 재귀를 적용한 알고리즘
function binarySearch(arr, key, left, right){
    if(left > right){
        return -1; // arr 를 끝까지 탐색했는데 못찾은 경우
    }
    
    let mid = Math.floor((left + right) / 2) // 중간 인덱스 값 설정(소수점 이하 버림)
    if(arr[mid] === key){ 
    	return mid; // key 를 찾은 경우
    } else if (arr[mid] < key){
    	return binarySearch(arr, key, mid+1, right); // 우배열을 탐색
    } else {
    	return binarySearch(arr, key, left, mid - 1); // 좌배열을 탐색
    }
}

 

1. 배열을 오름차순으로 정렬하고 시작한다.
2. Left, Right 값을 배열의 처음과 마지막 인덱스의 값을 할당해준다.  
3. Left > Right 가 더 크면 종료한다. (분할을 다했는데도 탐색키가 없다는 의미이기 때문이다)
4. 가운데 원소 값을 선언한다.
5. if, 배열의 가운데 원소와 x 를 비교해서 두 값이 같으면 탐색을 종료한다.
6. else, 가운데 원소 기준으로 왼쪽 / 오른쪽 두개의 부분 배열로 분할되고, 그 안에서
7.   If,  x 가 < 가운데 원소보다 작으면 왼쪽 부분배열에서 이진탐색을 다시 수행하고,
8.   else x 가 > 가운데 원소보다 크면 오른쪽 부분배열에서 이진탐색을 다시 수행한다.
9. 이러한 과정을 계속 재귀적으로 반복해서 원하는 값을 찾을 때까지 파고파고 들어가는 탐색을 수행한다.

 

반복문을 사용한 이진트리 알고리즘

// 반복 형태의 알고리즘
function binarySearch (arr, key) {
    let left = 0; // 배열의 시작인덱스
    let right = arr.length - 1; // 배열의 마지막 인덱스
    
    while(left <= right){ // 탐색 중일 때,
    	let mid = Math.floor((left + right) / 2); // 가운데 인덱스 재설정

        if(arr[mid] === key){ // 중간값과 key가 같다면
            return mid;       // key 를 찾은 경우
        } else if (arr[mid] < key){ // 중간값 < key 인 경우.
	        left = mid + 1; // 우배열 탐색을 위해 left 값을 중간값 다음 값으로 설정
        } else {
        	right = mid - 1; // 좌배열 탐색을 위해 right 값을 중간값 직전 값으로 설정
        }
    }
    
	return -1;
}