이분 탐색이란?

• 정렬된 배열에서 특정 값을 효율적으로 찾기 위한 탐색 알고리즘
• 탐색 범위를 절반씩 줄여가며 값을 찾아내기 때문에 시간 복잡도에서 효율적
• 탐색 대상 배열이 항상 정렬되어 있어야 하는 조건

이분 탐색의 동작 과정

1. 초기 설정: 배열의 시작점과 끝점을 설정한다.
2. 중간값 계산: 시작점과 끝점의 중간 인덱스 mid를 계산한다.
3. 비교: 배열의 중간 값(arr[mid])과 찾고자 하는 값(target)을 비교한다.
   • 값이 일치하면 중간값의 인덱스를 반환
   • 찾고자 하는 값이 더 작다면, 중간값보다 왼쪽에 있을 수 있으므로 끝점을 mid - 1로 이동
   • 찾고자 하는 값이 더 크다면, 중간값보다 오른쪽에 있을 수 있으므로 시작점을 mid + 1로 이동
4. 반복: 찾을 때까지 이 과정을 반복, 만약 탐색 범위가 줄어들어 시작점이 끝점보다 커지면, 배열에 값이 없다고 판단하고 종료.

이분 탐색 활용

• 데이터가 정렬되어 있고, 빠른 검색이 필요할 때.
  • ex) 정렬된 숫자 목록, 사전, 혹은 정렬된 문자열 목록에서 특정 단어를 찾는 경우

예시 코드

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const 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;  // 값을 찾지 못했을 때
}