이진 탐색 / 이분 탐색 (Binary Search)

• 이진 탐색은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.
• 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다.
• 이진 탐색의 시간 복잡도는 O(log N)
• 예시
  • [0, 2, 4, 6, 8, 10, 12, 14, 16, 18] 배열에서 원소 4를 찾는다면?
  • 인덱스 기준으로 시작점: 0, 끝점: 9, 중간점: 4 (소수점 이하 제거)
  • 찾고자 하는 값이 중간점을 기준으로 크기를 확인하고 탐색 범위를 설정한다.
    • 중간점보다 작다면: 시작점 ~ 중간점 전까지
    • 중간점보다 크거나 같다면: 중간점 ~ 끝점까지
  • 타겟 4는 중간점의 값인 8보다 작기 때문에 끝점의 위치를 기존의 중간점 직전(인덱스 3)으로 이동하고, 중간점도 새롭게 인덱스 1로 이동한다. (아래 그림 참고)
  • 탐색 범위를 줄여서 탐색 목표인 4가 중간점이 되면 탐색을 마친다.
    

이진 탐색 소스 코드 #1: 재귀적 구현 (JavaScript)

function binarySearch(arr, target, start, end) {
  if (start > end) return -1;
  const center = Math.floor((start + end) / 2);

  // 타겟을 찾은 경우 중간점 인덱스 반환
  if (arr[center] == target) {
    return center;
  // 중간점의 값이 타겟보다 큰 경우, 중간점을 끝점으로 설정 후 탐색
  } else if (arr[center] > target) {
    return binarySearch(arr, target, start, center - 1);
  // 중간점의 값이 타겟보다 작은 경우, 중간점을 시작점으로 설정 후 탐색
  } else {
    return binarySearch(arr, target, center + 1, end);
  }
}

const input = [0, 2, 4, 6, 8, 10, 12, 14, 16, 18];
const result = binarySearch(input, 4, 0, input.length - 1);

console.log(result == -1 ? '존재하지 않는 원소입니다.' : result + 1 + '번째 원소입니다.');

이진 탐색 소스 코드 #2: 반복문 구현 (JavaScript)

function binarySearch(arr, target, start, end) {
  while (start <= end) {
    const center = Math.floor((start + end) / 2);
    // 타겟을 찾은 경우 중간점 인덱스 반환
    if (arr[center] == target) {
      return center;
    // 중간점의 값이 타겟보다 큰 경우, 중간점을 끝점으로 설정
    } else if (arr[center] > target) {
      end = center - 1;
    // 중간점의 값이 타겟보다 작은 경우, 중간점을 시작점으로 설정
    } else {
      start = center + 1;
    }
  }
  return -1;
}

const input = [0, 2, 4, 6, 8, 10, 12, 14, 16, 18];
const result = binarySearch(input, 4, 0, input.length - 1);

console.log(result == -1 ? '존재하지 않는 원소입니다.' : result + 1 + '번째 원소입니다.');