코딩 테스트 탐색 이진탐색 완전탐색

// 이진 탐색(Binary Search) 구현 예제

/**
 * 반복문을 사용한 이진 탐색
 * @param {number[]} arr - 정렬된 배열
 * @param {number} target - 찾으려는 값
 * @returns {number} - 값의 인덱스 (없으면 -1)
 */
function binarySearchIterative(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 // 값이 없을 때
}

/**
 * 재귀를 사용한 이진 탐색
 * @param {number[]} arr - 정렬된 배열
 * @param {number} target - 찾으려는 값
 * @param {number} left - 탐색 시작 인덱스
 * @param {number} right - 탐색 종료 인덱스
 * @returns {number} - 값의 인덱스 (없으면 -1)
 */
function binarySearchRecursive(arr, target, left, right) {
  if (left > right) {
    return -1 // 값이 없을 때
  }

  const mid = Math.floor((left + right) / 2)

  if (arr[mid] === target) {
    return mid // 타겟 값을 찾음
  } else if (arr[mid] < target) {
    return binarySearchRecursive(arr, target, mid + 1, right) // 오른쪽 탐색
  } else {
    return binarySearchRecursive(arr, target, left, mid - 1) // 왼쪽 탐색
  }
}

// 배열과 타겟 값 예제
const sortedArray = [1, 3, 5, 7, 9, 11, 13]
const target = 7

// 반복문 사용
console.log('반복문 결과:', binarySearchIterative(sortedArray, target)) // 3

// 재귀 사용
console.log('재귀 결과:', binarySearchRecursive(sortedArray, target, 0, sortedArray.length - 1)) // 3