이진트리 BinarrySearch

정렬의 장점 → 바이너리 서치 (=이진 검색)

10을 찾는 거면 정렬이 되어 있으면 필요없는 왼쪽 데이터를 버리고 오른쪽 번지를 가서 탐색 5를 찾는 거면 정렬이 되어 있으면 필요없는 오른쪽 데이터를 버리고 왼쪽 번지를 가서 탐색

public class BinarryTest01 {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};

        final int target = 8;
        int N = arr.length;
        int start = 0;
        int end = N-1;

        int count = 0;

        for (int i = 0; i < N; i++) {
            count ++;
            int mid = start + (end-start)/2;
            if (arr[mid]==target){
                System.out.printf("target 값은 %d번지에 있습니다.\n", mid);
                break;
            }else if (arr[mid]<target){
                start = mid + 1;
            }else if (arr[mid]>target){
                end = mid - 1;
            }
        }
        System.out.printf("%d번만에 찾았습니다. ", count);


    }
}

• 시간복잡도 → 최대 반복 횟수 log₂(n) log₂(8) = 3 / 시간복잡도 = 3 log₂(16) = 4 / 시간복잡도 = 4
💡
이진트리는 선행적인 증가X, 시간복잡도 2의 제곱에 따라 1씩 증가
💡
전체 데이터의 15%미만인 경우 → 이진검색이 유리, 그 외에는 풀스캔 유리