HHyo814
발행일

[ZBF] 240619 코딩 테스트 : 이분탐색

코딩테스트

[ZBF] 240619 코딩 테스트 : 이분탐색

이 글은 네이버 블로그에 2024년 6월 18일에 올렸던 것을 그대로 옮겨온 것입니다.

이분탐색은 코딩 테스트에서 자주 등장하는 알고리즘 중 하나로, 정렬된 배열에서 특정 값을 효율적으로 찾기 위해 사용됩니다. 이분탐색을 잘 풀기 위해 알아야 할 개념과 방법을 단계별로 설명하겠습니다.

1. 이분탐색 기본 개념 이해하기

이분탐색(Binary Search)은 정렬된 배열에서 원하는 값을 찾기 위해 배열을 반복적으로 절반으로 나누는 방식입니다. 시간 복잡도는 O(log n)으로 매우 효율적입니다.

2. 이분탐색 알고리즘

이분탐색 알고리즘의 기본 원리는 다음과 같습니다:

  1. 배열의 중간 값을 선택합니다.
  2. 중간 값이 찾고자 하는 값과 같은지 확인합니다.
  3. 중간 값이 찾고자 하는 값보다 크다면 왼쪽 절반을 선택하고, 작다면 오른쪽 절반을 선택합니다.
  4. 반복적으로 위의 과정을 수행하여 값을 찾습니다.

3. 이분탐색 구현 방법

이분탐색은 반복문을 사용한 방법과 재귀를 사용한 방법 두 가지로 구현할 수 있습니다.

반복문을 사용한 이분탐색

// 이분탐색 (반복문 사용) 예제 (JavaScript)
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; // 값을 찾지 못한 경우 -1 반환
}

재귀를 사용한 이분탐색

// 이분탐색 (재귀 사용) 예제 (JavaScript)
function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
  if (left > right) {
    return -1; // 값을 찾지 못한 경우 -1 반환
  }

  let 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); // 왼쪽 절반 탐색
  }
}

4. 이분탐색 문제 해결 전략

이분탐색을 활용한 문제를 해결하기 위해 다음과 같은 전략을 사용할 수 있습니다.

문제 이해 및 조건 확인

먼저 문제를 잘 이해하고, 배열이 정렬되어 있는지, 탐색하려는 값의 범위가 어떤지 확인합니다. 이분탐색은 배열이 정렬되어 있어야 사용할 수 있습니다.

경계 조건 설정

이분탐색에서 경계 조건을 명확히 설정하는 것이 중요합니다. left, right, mid 값이 어떻게 변하는지 정확히 이해해야 합니다.

예외 처리

값을 찾지 못했을 경우에 대한 예외 처리를 명확히 합니다. 대부분의 경우 -1을 반환하거나 적절한 메시지를 출력합니다.

https://school.programmers.co.kr/learn/courses/30/parts/12486

  • 프로그래머스 스쿨 - 온라인 IT 특화 교육 전문 플랫폼 — 프로그래머스 스쿨은 IT 분야 교육 전반의 과정을 제공하는 온라인 교육 플랫폼입니다. 프로그래밍, 데이터, 인공지능 등의 학습부터 코딩 테스트, 과제 테스트 연습까지, 프로그래머스 스쿨과 함께 성장해 보세요!
← 글 목록으로