이진 탐색(Binary Search)

- 정렬된 상태의 데이터에서 특정 값을 빠르게 탐색하는 방법

1. 찾고자 하는 값과 데이터 중앙에 있는 값을 비교
2. 찾고자 하는 값이 더 작으면 데이터 왼쪽 부분에서 이진 탐색
3. 찾고자 하는 값이 더 크면 데이터 오른쪽 부분에서 이진 탐색

- 알고리즘 시간 복잡도 : O(log n)

❖ 구현

// 반복문 구조
    public static int binarySearch(int arr[], int target) {
        int left = 0;
        int right = arr.length -1;

        while(left <= right) {
            int mid = (left + right) /2;
            
            //오버플로우 방지
            // int mid = left + (right-left) /2;

            if(target == arr[mid]) {
                return mid;
            } else if(target < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return -left-1;
    }
    
    // 재귀 호출 구조
    public static int binarySearch2(int[] arr, int target, int left, int right) {
        if(left > right) {
            return -1;
        }

        int mid = (left + right) /2;

            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);
            }
    }
    
 
 // 자바에서 제공, 인덱스 반환
 // 찾는 데이터가 없는 경우 target값이 위치할 수 있는 인덱스에 -1하여 반환
 Arrays.binarySearch(arr, target);

 

❖ 원형 정렬 배열 이진 탐색

 // 원형 정렬 상태 배열에서의 이진 탐색
    // nums 배열에 원형 상태로 데이터가 정렬되어 있을 때,
    // 이진 탐색으로 데이터를 찾는 프로그램 작성
    // 배열 재 정렬 X
    public static int solution(int[] arr, int target) {
        if(arr == null || arr.length == 0) {
            return -1;
        }

        int left = 0;
        int right = arr.length-1;

        while(left <= right) {
            int mid = (left + right) /2;

            if(target == arr[mid]) {
                return mid;
            }

            // 4 5 6 7 0 1 2
            if(arr[left] < arr[mid]) {
                if(target >= arr[left] && target < arr[mid]) {
                    right = mid -1;
                } else {
                    left = mid +1;
                }
            } else {
            // 11 5 6 7 8 9 10
                if(target > arr[mid] && target <= arr[right]) {
                    left = mid + 1;
                } else {
                    right = mid -1;
                }
            }
        }
        return -1;
    }

 

❖ 2차원 행렬에서 이진 탐색

// row X col 행렬 데이터가 있을 때 target 이진 탐색으로 찾기
   // 각 행 데이터는 오름차순 정렬 상태

   // 행렬 : {{1, 3, 7, 8}, {10, 11, 15,20}, {21, 30, 35, 60}}
   // target : 3    출력 : true
    public static boolean solution(int[][] matrix, int target) {
        int left = 0;
        int rows = matrix.length;
        int cols = matrix[0].length;
        int right = rows * cols -1;

        while(left <= right) {
            int mid = (left + right) /2;

            if(matrix[mid/cols][mid%cols] == target) {
                return true;
            } else if(matrix[mid/cols][mid%cols] < target) {
                left = mid+1;
            } else {
                right = mid-1;
            }
        }
        return false;
    }

 

❖ 최소 적재량 계산

// 정수형 배열 weights와 정수 days가 주어졌다
   // weights에는 각 상품들의 무게들의 정보. days는 운송 납기일
   // weights에 적혀있는 순서대로 실어서 운송해야하는데
   // days 이내에 운송을 하기 위한 차량의 최소한의 적재량을 계산하는 프로그램
   // weights : 1 2 3 4 5 6 7 8 9 10
   // days : 5
   // 출력 : 15
   
    public static int solution(int[] weights, int days) {
        int left = 0;
        int right = 0;

        for(int i : weights) {
            left = Math.max(left, i);	// weights.length만큼 끊었을 때 최소 값, 그럼 하루마다
            right += i;					// 1일안에 적재 량
        }

        while(left <= right) {
            int mid = (left+right) /2;
            int sum = 0;
            int day = 1;

            for(int i = 0; i<weights.length; i++) {
                if(sum+weights[i] > mid) {
                    day++;
                    sum = 0;
                }
                sum += weights[i];
            }
            if(day > days) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return left;
    }

 

❖ 부분 배열의 값

// 정수형 배열 nums와 정수 m
    // nums에는 양의 정수 값, m은 배열을 부분 배열로 분리할 수 있는 수
    // nums를 m 개의 부분 배열로 분리할 때
    // 각 부분 배열의 합중 가장 큰 값이 최소가 되도록 분리했을 때의 합을 출력
    
    // nums : 7 2 5 10 8
    // m : 2
    // 출력 : 18

    // 부분 배열의 합 범위를 구해야함 
    // 2개로 나눴을 때 둘 중하나가 클 것인데 그 나누는 경우의 수 중에서 둘중 큰값이 제일 작은수
    public static int solution(int[] nums, int m) {
        int left = 0;
        int right = 0;

        for(int num : nums) {
            left = Math.max(num, left);     // 하나씩 분리하였을 때 가장 큰 값
            right += num;                   // 다 더했을 때
        }

        if( m == 1) {
            return right;
        }

        while(left <= right) {
            int mid = (left + right) /2;
            int cnt = 1;
            int total = 0;

            for(int num : nums) {
                total += num;
                if(total > mid) {
                    total = num;
                    cnt++;
                }
            }

            if( cnt <= m) {
                right = mid -1;
            } else {
                left = mid + 1;
            }

        }

        return left;
    }