[알고리즘] 이분탐색이란

이분탐색이란

대표적인 알고리즘중 하나로 탐색 범위를 두 부분으로 분활해 찾는 방식을 말합니다. 이분 매칭과 비슷한 원리로, 전체를 탐색하는 것에 비해 속도가 빠릅니다. 이분탐색은 left, right, mid 값을 이용해 탐색하게 되는데, mid를 기준으로 값을 비교해 탐색합니다. 이분탐색을 하기 위해선 값이 정렬이 되어있어야 합니다.

어떻게?

간단한 배열로 이분탐색을 살펴보겠습니다.
[1,2,3,4,5,6,7,8,9]
위와 같은 배열을 탐색하기 위해 우리는 메서드를 사용하지 않고, 원초적인 방법으로 탐색해 보겠습니다.

// 찾을 값 find = 3; 
// 찾을 배열 array = [1,2,3,4,5,6,7,8,9];
function arrFind(find, array){
//이미 정렬이 되어 있기에 정렬을 해줄필요 X
  let count = 0;
  
  for(let i = 0; i < array.length; i++){
  	count++;
    if(array[i] === find){
    	return count
    }
  }
}

다음과 같이 탐색을 했을 때 반복문을 돌며 배열을 검색해 find의 값과 같은 값을 찾았을 때 count를 리턴 해주는 방식으로 O(N)의 시간 복잡도가 필요합니다.

이분탐색

처음 말머리와 같이 이분 탐색은 left, mid, right 를 정해주고 mid가

//찾을 값 3;
//찾을 배열 array = [1,2,3,4,5,6,7,8,9];
function arrFind(find, array){
//이미 정렬이 되어 있기에 정렬을 해줄필요 X
  let count = 0;
  let left = 0;
  let right = array[array.length - 1];
  
  
  while(left <= right) {
    let	mid = Math.floor((right + left) / 2)
    
    if(mid === find) {
    	return count;
    }
    else if(mid > find) {
    	right = mid - 1;
      	count ++;
    }
    else if(mid < find) {
    	left = mid + 1;
      	count++;
    }
  
  }
  
}