Java 이진 탐색

소개

이진 탐색 (Binary Search) 은 정렬된 배열에서 값을 찾는 데 사용되는 효율적인 탐색 알고리즘입니다. 각 반복 후에 배열의 절반을 제거하기 때문에 선형 탐색 (linear search) 보다 빠릅니다. 이 Lab 에서는 Java 에서 이진 탐색 알고리즘을 구현하는 단계를 배우겠습니다.

정렬된 배열 생성

이진 탐색 알고리즘은 정렬된 배열을 필요로 하므로, 먼저 정렬된 배열을 생성합니다.

int[] sortedArray = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};

반복적 이진 탐색 구현

이제 이진 탐색 알고리즘을 반복적으로 구현해 보겠습니다. 이 메서드는 배열에 요소가 있으면 해당 요소의 인덱스를 반환합니다. 그렇지 않으면 -1 을 반환합니다.

public static int binarySearchIterative(int[] sortedArray, int key) {
    int leftIdx = 0;
    int rightIdx = sortedArray.length - 1;
    while (leftIdx <= rightIdx) {
        int midIdx = leftIdx + (rightIdx - leftIdx) / 2;
        if (sortedArray[midIdx] == key)
            return midIdx;
        else if (sortedArray[midIdx] > key) {
            rightIdx = midIdx - 1;
        } else
            leftIdx = midIdx + 1;
    }
    return -1;
}

코드를 실행하려면 먼저 binarySearchIterative 메서드를 호출하고, sortedArray와 검색하려는 요소를 매개변수로 전달해야 합니다.

## compile java file
javac BinarySearch.java

## run the file
java BinarySearch

재귀적 이진 탐색 구현

이제 이진 탐색 알고리즘을 재귀적으로 구현해 보겠습니다. 이 메서드 역시 배열에 요소가 있으면 해당 요소의 인덱스를 반환합니다. 그렇지 않으면 -1 을 반환합니다.

public static int binarySearchRecursive(int[] sortedArray, int key, int leftIdx, int rightIdx) {
    if (leftIdx <= rightIdx) {
        int midIdx = leftIdx + (rightIdx - leftIdx) / 2;
        if (sortedArray[midIdx] == key)
            return midIdx;
        else if (sortedArray[midIdx] > key) {
            return binarySearchRecursive(sortedArray, key, leftIdx, midIdx - 1);
        } else
            return binarySearchRecursive(sortedArray, key, midIdx + 1, rightIdx);
    } else
        return -1;
}

코드를 실행하려면 binarySearchRecursive 메서드를 호출하고, sortedArray, 검색하려는 요소, leftIdx, 그리고 rightIdx를 매개변수로 전달해야 합니다.

내장 함수를 사용한 이진 탐색

Java 에는 이진 탐색을 구현하기 위한 내장 함수도 있습니다. 이러한 함수는 Arrays.binarySearch()와 Collections.binarySearch()입니다. 정렬된 배열에서 요소를 검색하기 위해 이러한 함수를 사용할 수 있습니다.

Arrays.binarySearch() 함수는 정렬된 배열과 검색할 키 값을 매개변수로 사용합니다. 이 함수는 배열에 키가 있으면 해당 키의 인덱스를 반환합니다. 그렇지 않으면 -1 을 반환합니다.

int index = Arrays.binarySearch(sortedArray, 6);

Collections.binarySearch() 함수는 ArrayList 와 같은 컬렉션에서 요소를 검색하는 데 사용할 수 있습니다. 이 함수는 정렬된 컬렉션과 키를 매개변수로 사용하며, 키가 있는 인덱스를 반환합니다. 그렇지 않으면 -1 을 반환합니다.

ArrayList<Integer> sortedList = new ArrayList<Integer>(Arrays.asList(2, 4, 6, 8, 10, 12, 14, 16, 18, 20));
int index = Collections.binarySearch(sortedList, 6);

테스트

이제 모든 메서드를 테스트하고 출력을 인쇄합니다.

public static void main(String[] args) {
    int[] sortedArray = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
    int key = 12;
    System.out.println("Element " + key + " is present at index: " + binarySearchIterative(sortedArray, key));
    System.out.println("Element " + key + " is present at index: " + binarySearchRecursive(sortedArray, key, 0, sortedArray.length - 1));
    System.out.println("Element " + key + " is present at index: " + Arrays.binarySearch(sortedArray, key));
    ArrayList<Integer> sortedList = new ArrayList<Integer>(Arrays.asList(2, 4, 6, 8, 10, 12, 14, 16, 18, 20));
    System.out.println("Element " + key + " is present at index: " + Collections.binarySearch(sortedList, key));
}

코드를 실행하려면 먼저 Java 프로그램을 컴파일합니다.

javac BinarySearch.java

그런 다음 프로그램을 실행할 수 있습니다.

java BinarySearch

요약

이 랩에서는 Java 프로그래밍 언어에서 이진 탐색 알고리즘을 반복적 (iteratively) 및 재귀적 (recursively) 으로 구현하는 데 필요한 단계를 다루었습니다. 또한 이진 탐색을 구현하기 위한 내장 메서드인 Arrays.binarySearch() 및 Collections.binarySearch()에 대해서도 배웠습니다. 정렬된 배열을 생성하고 다양한 메서드를 사용하여 배열 내에서 요소를 검색했습니다.