• 앞에서부터 차례대로 탐색
  • 데이터가 정렬되어 있지 않을 경우 사용
  • 데이터가 많을수록 비효율적
  • O(n)
  • 정렬 후 중간값을 기준으로 필요없는 부분을 잘라내가며 탐색
  • 한번 탐색할때마다 대상이 절반(1/2)으로 줄어듬
  • 데이터가 많을수록 효율적
  • O(log n)
  • 결정 문제에 사용 된다 -> 정답의 범위가 주어지고 이진탐색으로 좁혀나가 최적의 해를 구한다 (파라매트릭 서치)
    • 결정 문제 : YES or NO 로 답할 수 있는 문제 -> mid값이 최적의 해인가? YES

방법

  1. 이분 탐색할 리스트를 정렬한다.
  2. 이분 탐색 범위의 시작(left)와 끝(right)를 초기화 한다.
    • 초기 값을 잘못 설정하면 오답을 유발한다
  3. mid 값을 도출해 이분 탐색 진행
  4. 결과에 따라 left=mid+1 or right=mid-1해서 다음회전 진행
  • 닫힌 범위 [0, n]
public int search(int[] nums, int target) {
    int left = 0, right = nums.length-1;

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

        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}
  • 열린 범위 (0, n) (★★중요★★)
public int search(int[] nums, int target) {
    int left = 0, right = nums.length;

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

        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

문제유형

1. 배열에 target이 있는 경우 (가장 basic 유형, 위 코드 확인)

2. 배열에 중복된 요소가 있는 경우

(1) 좌측 탐색 (가장 좌측값을 찾는 탐색, leftmost)

// [5,7,7,8,8,10], target = 8
// answer = 3
private int bisectLeft(int[] nums, int target) {
    int left = 0, right = nums.length;          

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

        if (nums[mid] >= target) {    // ★ 타겟일 경우 범위에 포함      
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    return left < nums.length && nums[left] == target ? left : -1;
}

(2) 우측 탐색 (가장 우측값을 찾는 탐색, rightmost)

// [5,7,7,8,8,10], target = 8
// answer = 4
private int bisectRight(int[] nums, int target) {
    int left = 0, right = nums.length;         

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

        if (nums[mid] > target) {           
            right = mid;
        } else {                     // ★ 타겟일 경우 범위에 포함하지 않음 
            left = mid + 1;
        }
    }

    return 0 < left && nums[left-1] == target ? left-1 : -1;
}

(3) 결정 문제 (파라매드릭 서치)

  • 문제에서 주어진 값의 범위를 한정 짓고(left/right) 해당 숫자(mid)가 답에 T/F인지 판단
  • 문제의 조건을 수정하여 가상의 FFFFFTTTTT 배열을 구상 할 수 있음
  • ex) FFFFFTTTTT 에서 가장 왼쪽의 T를 찾는 문제(=좌측 탐색)
public int smallestDivisor(int[] nums, int threshold) {
    // binary search (parametric search)
    int left = 1;
    int right = 0;
    for (int n : nums) {
        right = Math.max(n, right);
    }

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

        if (condition(mid, nums, threshold)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

private boolean condition(int divisor, int[] nums, int threshold) {
    int sum = 0;
    for (int num : nums) {
        sum += (num + divisor - 1) / divisor;
    }

    return sum <= threshold;
}