[알고리즘] 이진 탐색(Binary Search) 알고리즘

이진 검색 알고리즘(binary search algorithm)

오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘

처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택

처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 됨

단점 : 검색 원리상 정렬된 리스트에만 사용할 수 있음 (오름차순 정렬)

장점 : 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠름

 

 

즉, 무언가 찾고자하는 것이 있을 때 사용하는 알고리즘임

 

 

자바로 구현

 

방법1. 반복문으로 구현

    // 반복문 구조
    public static int binarySearch(int arr[], int target) {
        int left = 0; // left는 가장 초기로 초기화
        int right = arr.length -1; // right는 가장 끝으로 초기화

        while (left <= right) { // 반복문을 사용
            int mid = (left + right) / 2; // 초기 mid는 중앙값으로 설정

            if (target == arr[mid]) { // target이 딱 정중앙일 때 (첫트만에 성공)
                return mid;
            } else if (target < arr[mid]) { // target보다 클 때 -> mid가 최댓값이 됨(종점)
                right = mid -1; // mid를 최댓값으로 설정
            } else { // target보다 작을 때 -> mid를 새로운 최솟값으로 설정(시점)
                left = mid + 1;
            }
        }

        return -1;
    }

 

 

방법2. 재귀 호출 구조

    public static int binarySearch2(int[] arr, int target, int left, int right) {
        if (left > right){ // 바로 말이 안 되는 케이스
            return -1;
        }

        int mid = (left + right) / 2; // mid 중앙 설정은 동일

        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); // 최솟값을 새로 설정하는 것을 재귀를 통해 이용
        }
    }

 

 

자바 자체에서 패키지로 구성된 Binary Search

 

public class Main2 {
    public static void main(String[] args) {
        int[] arr = {1, 2, 5, 10, 20, 30, 40, 50, 60};

        System.out.println("== 데이터가 있는 경우 ==");
        // Arrays.binarySearch(배열, 타켓 키)
        System.out.println(Arrays.binarySearch(arr, 1));
        System.out.println(Arrays.binarySearch(arr, 10));
        System.out.println(Arrays.binarySearch(arr, 30));

        System.out.println("== 데이터가 없는 경우 ==");
        // 특이하게도 데이터가 없으면 그냥 null이나 false가 나오는 것이 아니라 삽입이 된다면 들어갈 수 있는 데이터의 위치를 알려줌
        // -가 붙은 채로 들어갈 수 있는 위치를 제공
        System.out.println(Arrays.binarySearch(arr, 3));
        System.out.println(Arrays.binarySearch(arr, 11));
        System.out.println(Arrays.binarySearch(arr, 111));
    }
}