[JS] 이진 검색

1. 이진 검색

 이진 검색(Binary Search)은 자료 가운데 있는 항목을 키 값과 비교하여 더 크면 오른쪽 부분을 검색하고, 키 값이 더 작으면 왼쪽 부분을 검색하는 방법이다. 이진 검색(Binary Search)은 퀵 정렬과 마찬가지로 분할과 정복 기법을 사용하기 때문에 시간 복잡도가 O(log₂N)으로 엄청나게 빠른 속도를 자랑한다. 하지만 이진 검색은 삽입, 삭제를 수행한 후에 항상 배열의 상태를 정렬된 상태로 유지해야 하는 작업이 따로 필요하다. 그 이유는 이진 검색(Binary Search)이 정렬된 순차 자료구조에서만 사용할 수 있기 때문이다.

 

2. 동작 순서

 퀵 정렬의 동작을 제대로 알고 있다면, 이진 검색(Binary Search)의 동작도 쉽게 이해할 수 있을 것이다. 이진 검색의 동작을 설명하기 위해 밑에 간단한 문제를 푸는 과정을 보여주도록 하겠다.

 

 

정렬되지 않은 순차 자료구조 [ 8, 9, 1, 2, 11, 19, 29]를 이진 검색을 이용해서 11을 찾으시오.

 

 

  먼저, 배열 [ 8, 9, 1, 2, 11, 19, 29 ]를 오름차순으로 모든 배열의 원소를 정렬하도록 하자.

 

[그림 1] 오름차순 정렬

 

 이제 정렬된 배열을 이진검색을 이용해서 11의 유무를 판별할 것이다. 정렬된 배열의 길이는 7이다. 7을 2로 나누면 3.5이므로 3을 가운데 값으로 받는다. 현재 배열의 인덱스 3에는 9가 저장되어 있다. 따라서 11과 9를 비교한다. 11은 9보다 크다. 그렇기 때문에 다음 검색 범위는 9의 오른쪽인 11에서 29까지다.

 

[그림 2] 이진 검색 1회

 

 다음 검색범위인 [11, 19, 29]를 다음과 같이 따로 커팅한다.

 

 

[그림 3] 3의 길이를 가지는 커팅한 배열

 

 커팅한 배열 [11, 19, 29]의 길이는 3이다. 3을 2로 나누면 1.5다. 따라서 가운데 값은 정수 부분만 추출한 1이된다. 이제 11과 인덱스 1에 저장된 19를 비교하도록 하자. 11은 19보다 작기 때문에 19의 왼쪽 부분인 11이 다음 검색범위가 된다.

 

[그림 4] 다음 검색 범위 결정

 

 다음 검색 범위인 11을 따로 커팅한다.

 

[그림 5] 커팅 배열

 

 커팅한 배열의 길이는 1이다. 1을 반으로 나누면 0.5다. 따라서 가운데 값은 0이된다. 이제 11과 인덱스 0에 위치한 11을 비교하도록 한다. 두 수는 같다. 따라서 검색을 성공으로 처리하고 이진 검색 작업은 종료된다. 만약에 찾는 키 값이 12라면, 이진 검색은 다음 과정으로 넘어갈 것이다. 그런데, 다음 과정으로 넘어가면 배열의 길이는 0이된다. 길이가 0인 배열은 검색에 실패했다는 뜻이므로, 실패 처리를 하고 이진 검색을 종료시키면 된다.

 

 

3. 프로그램 코드

const sorted = function(arr){
  return arr.sort((a,b) => a-b);
}

const binarySearch = function(arr, key){
  const middle = parseInt(arr.length/2);
  
  if(!arr.length)
    return false;

  if(arr[middle] === key)
    return true;
  else if(arr[middle] > key){
    //왼쪽 검색
    return binarySearch(arr.slice(0,middle), key);
  }
  else if(arr[middle] < key){
    //오른쪽 검색
    return binarySearch(arr.slice(middle+1), key);
  }
}

const main = (function(){
  const arr = [8, 9, 1, 2, 11, 19, 29];
  const key = 11;
  
  // 정렬
  sorted(arr);
  const isKey = binarySearch(arr, key);

  if(isKey)
    console.log("검색 성공!");
  else
    console.log("검색 실패ㅠㅠㅠㅠ");
}());

 

 

4. 참고 자료

 자바로 배우는 쉬운 자료구조, 한빛 아카데미