JavaScript와 Java의 이진 검색 마스터하기: 단계별 가이드

이진 검색은 모든 개발자가 이해해야 하는 기본 알고리즘으로 정렬된 배열에서 요소를 검색하는 매우 효율적인 방법을 제공합니다. 이 알고리즘은 "분할 및 정복" 접근 방식을 사용하므로 각 단계에서 검색 공간을 절반으로 줄일 수 있습니다. 이 기사에서는 JavaScript와 Java 모두에서 이진 검색을 탐색하고 반복 및 재귀 구현을 다룹니다.

이진 검색이란 무엇입니까?

이진 검색은 정렬된 배열 내에서 대상 값의 위치를 ​​찾기 위해 설계된 알고리즘입니다. 이진 검색은 배열의 정렬된 특성을 활용하여 검색 공간을 효율적으로 좁혀 O(log n)의 시간 복잡도를 달성합니다. 이는 대규모 데이터 세트의 선형 검색보다 훨씬 빠릅니다.

다음은 대략적인 개요입니다.

1. 현재 검색 범위를 나타내는 두 개의 포인터 startIndex 및 endIndex로 시작하세요.
2. startIndex와 endIndex 사이의 중간 지수(midIndex)를 계산합니다.
3. 중간 요소를 대상 요소와 비교합니다.
   • 대상과 일치하면 인덱스를 반환합니다.
   • 가운데 요소가 대상보다 큰 경우 대상은 왼쪽 절반에 있어야 하므로 endIndex를 조정하세요.
   • 가운데 요소가 타겟보다 작을 경우 타겟은 오른쪽 절반에 있어야 하므로 startIndex를 조정하세요.
4. 대상을 찾거나 startIndex가 endIndex를 초과하여 대상이 배열에 없음을 나타낼 때까지 프로세스를 반복합니다.

코드 예제를 살펴보겠습니다.

---

JavaScript 및 Java의 반복 이진 검색

루프를 좋아하시는 분들을 위해

자바스크립트 구현

JavaScript에서 반복 접근 방식은 루프를 사용하여 이진 검색을 수행합니다. 그 모습은 다음과 같습니다.

const binarySearch = (arr, target) => {
  let startIndex = 0;
  let endIndex = arr.length - 1;

  while (startIndex <= endIndex) {
    let midIndex = Math.floor((startIndex + endIndex) / 2);

    if (arr[midIndex] === target) {
      return midIndex; // Target found
    } else if (arr[midIndex] < target) {
      startIndex = midIndex + 1; // Search in the right half
    } else {
      endIndex = midIndex - 1; // Search in the left half
    }
  }
  return -1; // Target not found
};

let nums = [-1, 0, 3, 5, 9, 12];
console.log(binarySearch(nums, 9)); // Output: 4
console.log(binarySearch(nums, 2)); // Output: -1

자바 구현

Java에서 반복 구현은 Java 구문 조정을 제외하면 매우 유사합니다.

public class BinarySearchExample {

    public static int binarySearch(int[] arr, int target) {
        int startIndex = 0;
        int endIndex = arr.length - 1;

        while (startIndex <= endIndex) {
            int midIndex = (startIndex + endIndex) / 2;

            if (arr[midIndex] == target) {
                return midIndex; // Target found
            } else if (arr[midIndex] < target) {
                startIndex = midIndex + 1; // Search in the right half
            } else {
                endIndex = midIndex - 1; // Search in the left half
            }
        }
        return -1; // Target not found
    }

    public static void main(String[] args) {
        int[] nums = {-1, 0, 3, 5, 9, 12};
        int target = 9;

        int result = binarySearch(nums, target);
        if (result != -1) {
            System.out.println("Element found at index: " + result);
        } else {
            System.out.println("Element not found in the array.");
        }
    }
}

설명

두 구현 모두에서:

• startIndex와 endIndex를 각각 배열의 시작과 끝으로 설정합니다.
• 각 반복에서는 중간 인덱스인 midIndex를 찾고 arr[midIndex]를 대상과 비교합니다.
  • arr[midIndex]가 target과 같으면 midIndex를 반환합니다.
  • arr[midIndex]가 target보다 작으면 startIndex를 midIndex 1로 이동하여 검색 범위를 오른쪽 절반으로 좁힙니다.
  • arr[midIndex]가 target보다 크면 endIndex를 midIndex - 1로 이동하여 검색 범위를 왼쪽 절반으로 좁힙니다.
• startIndex가 endIndex를 초과하면 루프가 종료됩니다. 즉, 대상이 배열에 없음을 의미합니다.

---

JavaScript 및 Java의 재귀 이진 검색

재귀적 접근 방식의 경우 대상을 찾거나 검색 범위가 비어 있을 때까지 업데이트된 인덱스로 자신을 호출하도록 함수를 정의합니다.

인셉션을 좋아하시는 분들을 위해

자바스크립트 구현

JavaScript에서 재귀 이진 검색 구현은 다음과 같습니다.

const binarySearch = (arr, target) => {
  let startIndex = 0;
  let endIndex = arr.length - 1;

  while (startIndex <= endIndex) {
    let midIndex = Math.floor((startIndex + endIndex) / 2);

    if (arr[midIndex] === target) {
      return midIndex; // Target found
    } else if (arr[midIndex] < target) {
      startIndex = midIndex + 1; // Search in the right half
    } else {
      endIndex = midIndex - 1; // Search in the left half
    }
  }
  return -1; // Target not found
};

let nums = [-1, 0, 3, 5, 9, 12];
console.log(binarySearch(nums, 9)); // Output: 4
console.log(binarySearch(nums, 2)); // Output: -1

자바 구현

Java에서는 유사한 재귀 이진 검색을 다음과 같이 구현할 수 있습니다.

public class BinarySearchExample {

    public static int binarySearch(int[] arr, int target) {
        int startIndex = 0;
        int endIndex = arr.length - 1;

        while (startIndex <= endIndex) {
            int midIndex = (startIndex + endIndex) / 2;

            if (arr[midIndex] == target) {
                return midIndex; // Target found
            } else if (arr[midIndex] < target) {
                startIndex = midIndex + 1; // Search in the right half
            } else {
                endIndex = midIndex - 1; // Search in the left half
            }
        }
        return -1; // Target not found
    }

    public static void main(String[] args) {
        int[] nums = {-1, 0, 3, 5, 9, 12};
        int target = 9;

        int result = binarySearch(nums, target);
        if (result != -1) {
            System.out.println("Element found at index: " + result);
        } else {
            System.out.println("Element not found in the array.");
        }
    }
}

재귀 버전의 작동 방식

각 재귀 호출에서:

• 중간지수인 midIndex를 계산합니다.
• arr[midIndex]가 대상과 일치하면 인덱스를 반환합니다.
• arr[midIndex]가 대상보다 크면 왼쪽 절반에서 검색이 계속됩니다(endIndex는 midIndex - 1이 됩니다).
• arr[midIndex]가 대상보다 작으면 오른쪽 절반에서 검색이 계속됩니다(startIndex가 midIndex 1이 됩니다).
• 기본 사례 if(startIndex > endIndex)는 대상을 찾을 수 없는 경우 재귀가 중지되도록 보장합니다.

  ---

  복잡성 분석

  • 시간 복잡도: 반복 버전과 재귀 버전 모두 각 단계가 검색 공간을 절반으로 줄이므로 시간 복잡도는 O(log n)입니다.
  • 공간 복잡도: 반복적 접근 방식은 공간에 대해 O(1)인 반면, 재귀 접근 방식은 호출 스택으로 인해 O(log n)의 공간 복잡도를 갖습니다.

  이진 검색을 사용해야 하는 경우

  이진 검색은 다음과 같은 경우에 이상적입니다.

  • 배열이 정렬되었습니다: 이진 검색은 정렬된 배열에서만 작동합니다.
  • 효율성이 중요: O(log n) 시간 복잡도는 대규모 데이터세트에 매우 효율적입니다.

  배열이 정렬되지 않은 경우 먼저 정렬하거나(O(n log n) 비용으로) 데이터 세트가 작은 경우 선형 검색을 사용하는 것이 좋습니다.

  ---

  결론

  이진 검색은 정렬된 배열에서 요소를 찾기 위한 다양하고 효율적인 알고리즘입니다. 반복적 접근 방식을 선택하든 재귀적 접근 방식을 선택하든 이진 검색을 이해하는 것은 애플리케이션 성능을 향상시키는 데 중요합니다. JavaScript와 Java의 두 가지 구현을 모두 시도하여 작동 방식을 파악하고 특정 사용 사례에 가장 적합한 것이 무엇인지 확인하세요.

  ---

  ? 참조

  • 이진 검색
  • 그루킹 알고리즘
  • 빅오 표기법

  ? 나에게 말을 걸어

  • 링크드인
  • 깃허브
  • 포트폴리오

  위 내용은 JavaScript와 Java의 이진 검색 마스터하기: 단계별 가이드의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!