이진탐색(Binary Search)

이진탐색

이진탐색(Binary Search)은 정렬된 배열에서 특정한 값을 찾기 위한 알고리즘이다. 이 알고리즘은 반복적인 비교를 통해 원하는 값을 찾아낸다. 

 

이진탐색은 배열이 정렬되어 있어야만 사용할 수 있다. 정렬되어 있지 않은 배열에서는 값을 찾을 수 없다. 이 알고리즘은 정렬된 배열에서 원하는 값을 빠르게 찾아낼 수 있기 때문에, 대부분의 프로그래밍 언어에서 기본적으로 제공되는 정렬 알고리즘과 함께 많이 사용된다. 

 

이진탐색의 시간 복잡도는 O(log n)이다. 따라서 배열의 크기가 매우 크더라도, 비교횟수가 크게 늘어나지 않는다. 이는 다른 탐색 알고리즘들과 비교 했을 때 매우 효율적인 알고리즘이다. 

 

작동방식

1. 배열의 중간 값을 선택.
2. 중간 값이 찾고자 하는 값다 같다면 탐색을 종료.
3. 중간 값이 찾고자 하는 값보다 작으면, 배열의 오른쪽 절반을 기준으로 다시 탐색.
4. 중간 값이 찾고자 하는 값보다 크면, 배열의 왼쪽 절반을 기준으로 다시 탐색.
5. 찾고자 하는 값이 존재하지 않는 다면, 탐색을 종료.

 

코드

코드로 구현하는 방식은 두가지가 있다 반복문을 통한 구현 그리고 재귀호출을 통한 구현.

 

반복문 구조

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

    while (left <= right) {
        int mid = (left + right) / 2;

        if (target == arr[mid]) {   // 해당 데이터 찾음
            return mid;
        } else if (target < arr[mid]) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    // 해당 데이터 없는 경우
    return -1;
}

 

재귀함수 구조

public static int binarySearch2(int[] arr, int target, int left, int right) {
    if (left > right) { // 해당 데이터 없는 경우
        return -1;
    }

    int mid = (left + right) / 2;

    if (target == arr[mid]) {  // 해당 데이터 찾음
        return mid;
    } else if (target < arr[mid]) {
        return binarySearch2(arr, target, left, mid - 1);
    } else {
        return binarySearch2(arr, target, mid + 1, right);
    }
}

 

자바에서 제공하는 이진탐색 함수

자바에서 제공하는 이진탐색 함수는 `Arrays.binarySearch()` 이다. 이 함수는 배열에서 원하는 값을 찾아내는데 사용된다. 

 

`Arrays.binarySearch()` 함수는 아래와 같은 형식을 가지고 있다. 

public static int binarySearch(type[] arr, type key)

 

여기서 `arr`은 이진 탐색을 수행할 배열이며, `key`는 찾고자 하는 값을 나타낸다. `type`은 배열의 원소 타입을 나타내는데, 이진 탐색을 수행할 배열은 반드시 정렬되어 있어야 한다.

 

`Arrays.binarySearch()` 함수는 찾고자 하는 값이 존재하는 경우, 해당 값을 가지는 배열 요소의 인덱스를 반환한다. 그렇지 않은 경우, `(해당 데이터가 있을 경우의 위치) -1`을 반환한다.

int[] arr = {1, 2, 5, 10, 20, 30, 40, 50, 60};

System.out.println("== 데이터가 있는 경우 ==");
System.out.println(Arrays.binarySearch(arr, 1)); // 0
System.out.println(Arrays.binarySearch(arr, 10)); // 3
System.out.println(Arrays.binarySearch(arr, 30)); // 5


System.out.println("== 데이터가 없는 경우 ==");
// -1 반환이 아닌 '-(해당 데이터가 있을 경우의 위치) - 1'을 반환
System.out.println(Arrays.binarySearch(arr, 3)); // -3
System.out.println(Arrays.binarySearch(arr, 11)); // -5
System.out.println(Arrays.binarySearch(arr, 35)); // -7

 

`Arrays.binarySearch()` 함수는 오버로딩이 되어 있어서, 탐색의 시작 위치와 종료 위치를 지정할 수 있다. 또한, 배열이 정렬되어 있지 않은 경우에도 이진탐색을 수행 할 수도 있도록 `Comparator` 인터페이스를 구현한 객체를 이용하여 탐색이 가능하다.

public static int binarySearch(type[] arr, int fromIndex, int toIndex, type key)
public static int binarySearch(type[] arr, type key, Comparator<? super type> c)
public static int binarySearch(type[] arr, int fromIndex, int toIndex, type key, Comparator<? super type> c)

 

여기서 지네릭스에 구현된 `<? super type>`은 해당 타입에 해당하는 값들만 정렬은 한다는 의미로 하나의 부모클래스로 여러 자식클래스들이 존재할 때 유용하게 사용이 가능하다. 

 

아래의 코드는 문자열 배열을 정렬하여 이진탐색을 할 때, 대소문자를 구분하지 않고 비교하고 싶은 경우를 생각하여 만든 코드이다. 

import java.util.Arrays;
import java.util.Comparator;

public class Example {
    public static void main(String[] args) {
        String[] arr = {"apple", "banana", "Cherry", "DATE", "Elderberry", "Fig", "GRAPE"};

        // 대소문자를 구분하지 않고 비교하는 Comparator 인터페이스를 구현한 객체 생성
        Comparator<String> ignoreCaseComp = new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                return s1.compareToIgnoreCase(s2);
            }
        };

        // 배열을 대소문자를 무시하고 정렬
        Arrays.sort(arr, ignoreCaseComp);

        // 대소문자를 무시하고 이진탐색 수행
        int index = Arrays.binarySearch(arr, "DATE", ignoreCaseComp);
        System.out.println("Index of \"DATE\": " + index); // Index of "DATE": 3
    }
}