이진 탐색

이진 탐색

 

: 데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘

• 대상 데이터의 중앙 값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다. → 업/다운 게임
• 시간 복잡도 - O(logN)

 

 

이진 탐색 동작 방식 (오름차순)

1. 현재 데이터셋의 중앙 값을 선택한다
2. 중앙 값 > 타깃 데이터 일 때 중앙 값 가준으로 왼쪽 데이터셋을 선택한다.
3. 중앙 값 < 타깃 데이터 일 때 중앙 값 기준으로 오른쪽 데이터셋을 선택한다.
4. 과정 1~2를 반복하다가 중앙값 == 타깃 데이터일 때 탐색을 종료한다.

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

💡 left = mid + 1이고, right = mid - 1인 이유 → mid는 target을 포함할 숫자 범위에서 명확히 제외되기 때문 !