[java] 자바로 이분 탐색 알고리즘 구현하기

15 Dec 2023

java

이분 탐색 알고리즘은 정렬된 배열에서 원하는 항목을 빠르게 찾는 방법입니다. 배열의 중간 요소를 선택하고, 찾고자 하는 값과 비교하여 해당 요소를 제거하는 방식을 계속 반복합니다.

이분 탐색 알고리즘 구현

다음은 자바로 이분 탐색 알고리즘을 구현한 예제 코드입니다.

public class BinarySearch {
    public 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;
            else if (arr[mid] < target)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return -1;
    }
}

위의 코드에서 binarySearch 메서드는 정렬된 정수 배열과 찾고자 하는 값(target)을 입력으로 받아 이분 탐색을 수행합니다.

사용 예제

다음은 BinarySearch 클래스를 사용하는 예제 코드입니다.

public class Main {
    public static void main(String[] args) {
        int[] arr = {2, 4, 6, 8, 10, 12, 14, 16};
        int target = 10;
        
        BinarySearch bs = new BinarySearch();
        int result = bs.binarySearch(arr, target);
        
        if (result == -1)
            System.out.println("찾고자 하는 값이 배열에 존재하지 않습니다.");
        else
            System.out.println("찾고자 하는 값은 배열의 인덱스 " + result + "에 있습니다.");
    }
}

위의 코드는 {2, 4, 6, 8, 10, 12, 14, 16} 배열에서 10을 찾는 예제를 보여줍니다.

결론

이분 탐색 알고리즘은 데이터가 정렬된 상태에서 사용 가능하며, 선형 탐색보다 효율적으로 원하는 항목을 찾을 수 있습니다. 위의 예제 코드를 참고하여 자신만의 이분 탐색 알고리즘을 만들어보세요.

참고: GeeksforGeeks - Binary Search