[java] 자바의 이분 탐색(Binary Search) 알고리즘 이해하기

14 Dec 2023

java

이분 탐색은 정렬된 배열에서 특정 요소를 찾는 알고리즘입니다. 배열의 중간 요소와 찾으려는 값의 크기를 비교하여 절반씩 탐색 범위를 줄여가며 탐색합니다. 이 알고리즘은 O(log n)의 시간 복잡도를 가지므로, 매우 효율적인 탐색 알고리즘으로 널리 사용됩니다.

이분 탐색 알고리즘 구현

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

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

            if (arr[mid] == target) {
                return mid;
            }

            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1; // 찾고자 하는 요소가 배열에 없을 경우
    }
}

이분 탐색 알고리즘 예시

다음은 이분 탐색 알고리즘을 사용하여 배열에서 특정 값의 인덱스를 찾는 예시입니다.

int[] arr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int target = 23;
int result = BinarySearch.binarySearch(arr, target);
System.out.println("찾고자 하는 값의 인덱스: " + result);

결론

이분 탐색 알고리즘은 정렬된 배열에서 빠르게 원하는 값을 찾을 수 있는 강력한 알고리즘입니다. 이를 이용하여 대용량 데이터나 검색이 빈번한 경우에 효율적인 탐색을 할 수 있습니다. Java에서는 기본적으로 제공되는 Arrays.binarySearch() 메서드를 통해서도 쉽게 이분 탐색을 수행할 수 있습니다.

더 많은 내용을 원하시거나 다른 종류의 탐색 알고리즘에 대해 관심이 있다면, GeeksforGeeks 등의 사이트에서 참고 자료를 찾아보시는 것을 추천드립니다.