[java] 자바를 활용한 이진 탐색 알고리즘

15 Dec 2023

java

이진 탐색(Binary Search)은 정렬된 배열에서 원하는 항목을 찾는 데 사용되는 효율적인 알고리즘입니다. 정렬된 배열에서 중간 항목을 선택하고 찾고자 하는 값과 비교하여 다음 검색 위치를 결정하는 방식으로 동작합니다.

이진 탐색 알고리즘의 원리

이진 탐색 알고리즘은 다음과 같은 단계로 동작합니다:

배열의 중간 요소를 선택합니다.
중간 요소와 찾고자 하는 값과 비교합니다.
중간 요소가 찾고자 하는 값과 일치하면 해당 요소의 인덱스를 반환합니다.
중간 요소가 찾고자 하는 값보다 작다면, 중간 요소의 오른쪽에만 존재할 수 있으므로, 배열의 오른쪽 반만 다시 탐색합니다.
중간 요소가 찾고자 하는 값보다 크다면, 중간 요소의 왼쪽에만 존재할 수 있으므로, 배열의 왼쪽 반만 다시 탐색합니다.
탐색 범위가 축소될 때까지 위의 과정을 반복합니다.

자바로 이진 탐색 알고리즘 구현하기

다음은 자바를 사용하여 정렬된 배열에서 이진 탐색 알고리즘을 구현하는 예시 코드입니다.

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;
            }

            if (arr[mid] > target) {
                right = mid - 1;
            }
        }

        return -1; // 찾고자 하는 값이 배열에 존재하지 않을 경우
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 5, 8, 10, 15, 18};
        int target = 8;
        int result = binarySearch(arr, target);
        if (result == -1) {
            System.out.println("찾고자 하는 값이 배열에 존재하지 않습니다.");
        } else {
            System.out.println("찾고자 하는 값의 인덱스: " + result);
        }
    }
}

위의 예시 코드에서 binarySearch 메소드는 이진 탐색 알고리즘을 구현한 것으로, 주어진 배열에서 목표 값의 인덱스를 반환하거나 값이 배열에 존재하지 않을 경우 -1을 반환합니다.

이진 탐색 알고리즘은 탐색 범위를 반으로 줄여가며 빠르게 원하는 항목을 찾을 수 있는 장점이 있습니다. 이를 토대로 개발시에는 데이터 검색에 이 알고리즘을 적용하여 검색 속도를 향상시킬 수 있습니다.

이진 탐색 알고리즘에 대한 보다 자세한 내용은 GeeksforGeeks에서 확인할 수 있습니다.