이진탐색 알고리즘

이진탐색이란 ?

divide and conquer(분할 정복) 패턴을 지향하는 탐색 알고리즘. 빠르고 효율적이지만 배열이 정렬되어있어야 한다.

시간복잡도는 O(log n)

 

준비물

정렬된 배열 Array A 와 Left, Middle, Right 포인터

 

동작원리

L: 배열의 첫번째, R: 배열의 마지막, M: L 와 R의 평균값

If A[M] === target return M 

If A[M] < target, set L to M+1 -> 미들 다음으로 탐색

If A[M] > target, set R to M-1 -> 미들 이전을 최고값으로 탐색

 

const nums = [1,5,13,17,32,39,45,50]

function binarySearch(arr: number[], target: number){
  let left = 0;
  let rignt = arr.length - 1;
  while(left <= right){
    let middle = Math.floor((left+right)/2)
    if(arr[middle] === target){
      return middle
  } else if(arr[middle] < target){
    left = middle + 1
  } else {
    right = middle - 1
  }
  return -1;
}

binarySearch(nums, 45) // 6
binarySearch(nums, 70) // -1