JavaScript 알고리즘 (11) Binary Search

 

 

 

요즘 알고리즘 공부하는 맛을 알게 된 새발자🐣

처음에는 아무것도 모르고 듣기만 했는데, 2번 보고 3번 보니 이해가 가면서 재미가 있다.

 

오늘은 Searching Algorithm 의 두번째 방법인 Binary Search (2진 탐색) 을 공부해보았다.

Linear search 가 1번부터 순서대로 검사하는 방식이었다면,

Binary search 는 가운데에서 반으로 쪼개서 검사한다. (고구마 먹을 때 반으로 쪼개서 먹듯이)

 

핵심만 말하자면 배열을 반으로 쪼개서 둘중 하나를 계속 버리고 또 쪼개서 버리고 이런식으로 추려나간다.

The algorithm is based on a well know domain divide and conquer technique.
It repeatedly breaks down the array in two sub-arrays which might contain the element we need and discards the other sub-array, and this goes on till the array size becomes 0 or till the element is found!

언뜻봐도 답을 찾을 때까지 반으로 쪼개고 또 쪼개는 것을 알수있다.

 

function binarySearch(arr, elem){ // 매개변수로 배열 전체와 elem(찾을 숫자)를 받는다.
  var start = 0; 		  // 시작점 설정 
  var end = arr.length - 1; 	  // 끝점 설정
  var middle = Math.floor((start + end) / 2); // 중간점 설정

  // while 문을 돌리자 (중간점이 찾는 숫자에 도달못했고 && 시작점과 끝점이 건재할 때까지만)
  while(arr[middle] !== elem && start <= end) { 
    if(elem < arr[middle]){ // if 반으로 쪼갯을때 찾는 숫자가 중간점보다 작으면
      end = middle -1;      // 끝점은 중간보다 하나 작은 수로 리셋하고
    } else {		    // else 반으로 쪼갯을때 찾는 숫자가 중간점보다 크면
      start = middle + 1;   // 시작점을 중간보다 하나 큰 수로 리셋하자 
    }

    middle = Math.floor((start + end) / 2) // 그리고 중간점을 다시 재설정하자
  }      

  if(arr[middle] === elem) { // 만약 중간점이랑 elem 이 같으면 
    return middle;	     // 그대로 중간점 인덱스를 리턴하자
  }

  return -1; 	// 그외 나머지경우는 -1 로 처리 (이상한 숫자 넣거나 undefined 등의 예외)
}

binarySearch([2, 5, 6, 9, 13, 15, 28, 30], 28) // 6 (인덱스 6을 리턴)

 

Big o notation 에서는 아래와 같이 표기할 수 있다.

Best - O(1)  // 한방에 찾는 경우 
Average - O(log n)
Worst - O(log n)