Tag: binary search

이진 탐색과 구현방법

이진 탐색(binary search)은 데이터 집합에서 원하는 데이터를 찾을 때까지 집합을 이분(二分)하여 탐색하는 방법입니다.

데이터 집합을 둘로 나누고 찾는 데이터가 있는 집합을 선택하여 다시 반으로 나누고 다시 데이터가 있는 집합에 같은 과정을 계속 반복합니다.

따라서 아무리 큰 데이터라도 몇 번의 연산만으로 원하는 데이터를 찾을 수 있습니다.

하지만 이진 탐색은 조건이 있는데요.

데이터가 반드시 순서대로 정렬된 상태여야 합니다.

그림을 통해 탐색의 과정을 확인해 보겠습니다.

위와 같은 데이터 집합에서 2를 찾으려면 먼저 집합을 반으로 나누고 찾는 데이터가 속한 집합을 선택합니다.

그럼 첫 번째로 선택한 집합은 다음과 같습니다.

또 반을 나누고 2가 속한 집합만을 선택합니다.

여기서 반을 나누고 2가 속한 집합을 선택하면 다음과 같습니다.

이제 둘 중 하나를 확인하여 원하는 데이터를 선택하면 됩니다.

이진 탐색 코드는 다음과 같습니다.

const binarySearch=(target, data)=>{

  let low = 0;
  let high = data.length-1;
  
  while(low<=high){
    
    let mid = Math.floor((low+high)/2);    
  
    if(target===data[mid]){
       return mid;
    }else if(target>data[mid]){
      low = mid+1 
    }else if(target<data[mid]){
      high = mid-1
    }
  }

  return undefined;
}

이 탐색 방법은 데이터의 양이 많아지면 엄청난 효율을 자랑합니다.

데이터가 10000까지 있을 때 8000을 찾기 위해서 무차별 대입은 7999번의 연산을 진행해야 하지만 이진 탐색 방법은 13번의 연산이면 원하는 데이터를 찾을 수 있습니다.