[Algorithm] 이진탐색 알고리즘 (Binary Search Algorithm)

1. 이진탐색(Binary Search)

 

이분탐색이라고도 불리는 이진탐색 알고리즘은, 정렬된 배열 내에서 대상 값의 위치를 찾는 검색 알고리즘이다.

대상 값을 배열의 중간 요소와 비교한 후, 동일하지 않으면 절반을 제거하고 이를 성공할 때까지 반복한다. 

 

정렬된 배열을 앞에서부터 하나하나 순차적으로 탐색하는 것을 순차탐색이라 하는데,

이러한 순차탐색보다 좀 더 빠르게 위치를 찾을 수 있다.

 

이진탐색의 시간복잡도는 O(log(n))이다. 

(순차탐색의 시간복잡도는 O(n))

 

 

2. 이진탐색 구현

function solution(target, arr) {
    let answer;
    arr.sort((a, b) => a - b);

    //인덱스번호
    let lt = 0, rt = arr.length - 1;
    while (lt <= rt) {
        let mid = parseInt((lt + rt) / 2);
        if (arr[mid] === target) {
            answer = mid + 1;
            break;
        }
        else if (arr[mid] > target) rt = mid - 1
        else lt = mid + 1
    }

    return answer;
}

let arr = [23, 87, 65, 12, 57, 32, 99, 81];
console.log(solution(32, arr));

 

자바스크립트로 이진탐색 구현하는 방법이다.

하나씩 살펴보자. 

 

arr.sort((a, b) => a - b);

 

이분탐색의 경우 무조건 해당 배열이 정렬되어 있어야 한다.

따라서 sort를 이용해 배열을 내림차순으로 정렬해준다.

 

 

let lt = 0, rt = arr.length - 1;

 

이진탐색은 배열의 가운데 값을 찾는 값과 비교한 후, 절반을 자르면서 정렬하는 알고리즘이다.

가운데 값을 찾기 위해선 각 끝 점의 index 를 알아야 하기 때문에 이를 가리키는 lt, rt 변수를 만들어준다.

 

lt는 왼쪽 끝, 즉 시작점을 가리키기 때문에 0을 넣어주고,

rt는 오른쪽 끝, 즉 맨 마지막 값을 가리키기 때문에 arr.length - 1을 넣어준다.

 

 

while(lt <= rt) { ... }

 

이제 while문을 통해 이분탐색을 구현해 준다.

이분탐색은 배열을 잘라가면서 값을 찾기 때문에 각 끝점이 결국엔 만나게 된다.

 

따라서 조건문을 lt <= rt로 설정해 준다.

 

 

let mid = parseInt((lt + rt) / 2);

 

그 후, 가운데 값을 찾아준다. 각 끝점을 더한 값을 2로 나눈 후, parsenInt를 통해 정수 값만 남겨준다.

(lt + rt = 잘린 arr.length) 

 

 

if (arr[mid] === target) {
    answer = mid + 1; 
    break; 
}
else if (arr[mid] > target) rt = mid - 1; 
else lt = mid + 1;

 

배열의 가운데 값(arr[mid])이 찾는 값(target)과 같다면, 값을 리턴해준다.

이때 mid의 값은 인덱스 번호이므로 + 1을 해줘야 한다.

 

가운데 값(arr[mid])이 찾는 값(target) 보다 크다면, 찾는 값은 앞쪽에 있기 때문에 rt를 움직여 배열을 잘라준다.

현재 가운데 값도 제외해야 하기 때문에 mid - 1을 rt에 넣어준다.

 

마지막으로 가운데값(arr[mid])이 찾는 값(target) 보다 작다면, lt를 움직여 배열을 잘라준다.

마찬가지로 가운데 값을 제외해야 하기 때문에 mid + 1을 lt에 넣어준다.