이진트리 서치(binary 서치)

package ex03.test;

public class BinaryTest01 {
    public static void main(String[] args) {
        //이진 검색 ==> 반드시 정렬이 되어 있어야 한다.
        int[]arr = {1, 2, 3, 4, 5, 6, 7, 8,9}; // 9/2 = 4 4번 인덱스를 찾을 8과 비교해보고 작으니 4번인덱스 뒤에 있는 기준점을찾는다.


        //target = 8

        // 0번지 ~ 8번지
        // mid = N /2 = 4 -> arr[4] -> 값 : 5
        // if(8==5) ->mid 위치에 타겟이 있다.
        // if(8>5) 참


        // 5번지 8번지
        // mid = arr[7] --> 값 =8
        // if(8==8) ->mid 위치에 타겟이 있다.
        // if(8>8)


    }
}

시간 복잡도

package ex03;

public class BinarySearch {
    public static void main(String[] args) {
        // N = 21
        // 시간복잡도 log2(N) -> log2(21) -> 4.x
        // 이진 검색 => 반드시 정렬이 되어 있어야 한다.
        // 21 / 2*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 = 3; // 10, 4, 1, 2, 3
        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)));
    }
}