018_이진 검색(BinarySearch)

Dec 18, 2023

Contents

정렬된 데이터 집합에서 특정 값을 빠르게 찾는 검색 알고리즘이다.

알고리즘은 '분할 정복' 전략을 사용하여 검색 범위를 반으로 줄여나가며 원하는 값을 찾는 방식으로 작동한다.

시간 복잡도는 log2(n) 이때 n은 배열의 개수이다. 한마디로 배열 하나를 늘린다고 시간이 1씩 증가 하는게 아니라는 것이다.

☝

데이터가 많아 질수록 풀스캔 보다 이진 검색이 유리하다. 하지만! 찾아야 하는 데이터의 수에 따라서 풀스캔과 이진트리의 효율성이 달라진다! → 이진 트리는 찾아야 하는 데이터가 많이 질수록 풀스캔 보다 더 많이 조회하므로 효율이 떨어진다. (이진 트리는 동일한 것을 찾을 때는 오래 걸린다.) → 데이터가 많아질수록 풀스캔 보다 이진 트리이 유리하다. 이유! 시간 복잡도를 보면 쉽게 이해가 가능하다! 풀스캔 → O(N) 인덱스스캔 → O(logN) 전체 데이터의 15프로 이하면 인덱스 스캔(이진 검색)이 더 빠르다! ex) log2(20) = 5(4.x) 이므로 20개의 데이터를 조회할 때 인덱스 스캔으로 3개 까지는 더 유리한데 4개 이상부터는 풀스캔이 유리하다.

이진 검색 예제


package ex03;

public class BinarySearch {
    public static void main(String[] args) {
        // N = 21
        // 시간복잡도 log2(N) -> log2(21) -> 4.x (max를 의미함)
        // 이진 검색 => 반드시 정렬이 되어 있어야 한다.
        // 21 / 2*2*2*2*2 -> logn -> log21
        int[] arr = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
        int N = arr.length;
        final int target = 2;
        int start = 0;
        int end = N - 1;
        int mid;

        int round = 1;
        while (true) {
            // 1 회전
            mid = start + ((end - start) / 2); // 기대값 7
            System.out.println("mid : " + mid);

            if (arr[mid] == target) {
                System.out.println(round + "회전 : " + target + "값은 " + mid + "번지에 있습니다");
                break;
            }

            if (arr[mid] < target) { // 기대값 start 5, end 8
                start = mid + 1;
            }

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

            System.out.println(round + "회전 start : " + start);
            System.out.println(round + "회전 end : " + end);

            round++;
        }

        System.out.println("시간복잡도 : " + (Math.log(N) / Math.log(2)));
    }
}

출력 결과

외워 두면 좋을 것!

log2(8) = 3 log2(16) = 4 log2(65536) = 16

O(N) O(1) O(logN)

package ex03; public class BinarySearch { public static void main(String[] args) { // N = 21 // 시간복잡도 log2(N) -> log2(21) -> 4.x (max를 의미함) // 이진 검색 => 반드시 정렬이 되어 있어야 한다. // 21 / 2*2*2*2*2 -> logn -> log21 int[] arr = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}; int N = arr.length; final int target = 2; int start = 0; int end = N - 1; int mid; int round = 1; while (true) { // 1 회전 mid = start + ((end - start) / 2); // 기대값 7 System.out.println("mid : " + mid); if (arr[mid] == target) { System.out.println(round + "회전 : " + target + "값은 " + mid + "번지에 있습니다"); break; } if (arr[mid] < target) { // 기대값 start 5, end 8 start = mid + 1; } if (arr[mid] > target) { end = mid - 1; } System.out.println(round + "회전 start : " + start); System.out.println(round + "회전 end : " + end); round++; } System.out.println("시간복잡도 : " + (Math.log(N) / Math.log(2))); } }