[JAVA] 이진 탐색,이분 검색 (Bianary Search)

import java.util.Scanner;

public class BinaryTest02 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9};
        System.out.print("정수를 입력하세요 (1~9) : ");
        int target = sc.nextInt();
        int count= 1;
        int start = 0;
        int end = arr.length-1;
        int mid;

        for (;; count++) {              // 무한 루프, 비교 횟수 카운트
            mid = (start+end)/2;        // 시작
            if (arr[mid] == target)
                break;
            else if (arr[mid] < target)
                start = mid+1; // 중요
            else
                end = mid-1;   // 중요2
        }

        System.out.printf("정수는 %d번지에 있습니다.\n", mid);
        System.out.printf("비교 회수 : %d", count);
    }
}

주의 ※ 데이터 분포도에 따라 2진 탐색보다 풀스캔이 빠를 수도 있다. ex) 여러개의 데이터를 찾을 때 등 전체 데이터의 15%미만인 경우, 2진 탐색이 시간 복잡도가 더 빠르다. 무조건 빠른건 안니다

public static void main(String[] args) {

        // N = 13
        // 시간복잡도 log2(N) -> log2(13) -> 3.700 (3과 4사이)
        // 이진 검색 => 반드시 정렬이 되어 있어야 한다.
        // 21 / 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 = 3;
        int start = 0;
        int end = N - 1;
        int mid;

        int round = 1;
        while (true) {
            // 1 회전
            mid = start + ((end - start) / 2); // 기대값 6
            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)));
    }

결론, 전체 데이터의 15%미만인 경우, 2진 탐색이 시간 복잡도가 더 빠르다