선형 탐색 / 이진 탐색

JavaScript 알고리즘 & 자료구조 마스터클래스

 

1. 선형 탐색 O(n)

배열에서 원하는 값을 찾는 방법으로 제일 단순한 것은 앞에서부터 하나씩 순서대로 살펴보는 것이다.

js 내장 함수인 indexOf, includes 등이 선형 탐색으로 만들어져 있다.

indexOf를 직접 구현해 보면 아래와 같다.

function myIndexOf(arr, target){
  for(let i = 0; i < arr.length; i++){
    if(arr[i] === target){
      return i
    }
  }

  return -1
}

선형 탐색의 big O는 최선의 경우는 O(1), 최악의 경우와 평균은 O(n)이다.

 

2. 이진 탐색

분할 정복 패턴으로, 확인할 때마다 절반을 지울 수 있다. → 정렬되어 있어야 함

 

function binarySearch(arr, target){
  let left = 0
  let right = arr.length
  let mid

  while(left < right){ // 중단 조건
    mid = parseInt((left + right) / 2)

    if(arr[mid] === target){
      return mid // 해당하는 인덱스 리턴
    }

    // 나머지 절반만 찾기 위해 포인터 조정
    arr[mid] > target ? right = mid - 1 : left = mid +1 
  }

  return -1 // 배열에 타겟이 없을 경우
}

이진 탐색은 최악의 경우와 평균의 경우 O(log n) 를 가진다.