이분검색(binary search)

🗒️이분검색

처음과 마지막의 중간 값을 찾고자 하는 숫자와 비교하여, 중간값이 더 크면 그 값을 최댓값으로, 작으면 최솟값으로 설정하여 반복한다.

반드시 오름차순으로 정렬된 리스트이여야 하다.

모든 값을 순회하는 일반 검색의 시간복잡도는 O(n)인데 반해,
이분검색의 시간복잡도는 O(log n)이다.

🔍 java코드 구현

public int solution(int n, int target, int[] arr) {
    int minIndex = 0, maxIndex = n-1;
    Arrays.sort(arr);

    while (minIndex <= maxIndex) {
        int halfIndex = (minIndex + maxIndex) / 2;
        if (arr[halfIndex] < target) {
            minIndex = halfIndex+1;
        } else if (arr[halfIndex] > target) {
            maxIndex = halfIndex-1;
        } else return halfIndex + 1;
    }
    return 0;
} 

💡팁
minIndex와 maxIndex는 중간값보다 반드시 1크거나 작게 설정해주어야 한다.
그렇지 않으면 list에 없는 값이 들어왔을 경우 영원히 종료되지 않는다.
없는 값이 들어오면 min값 max값이 보다 커지며 반복문이 종료된다.

✏️이분검색 문제 (결정알고리즘)

* 설명
지니레코드에서는 불세출의 가수 조영필의 라이브 동영상을 DVD로 만들어 판매하려 한다.
DVD에는 총 N개의 곡이 들어가는데, DVD에 녹화할 때에는 라이브에서의 순서가 그대로 유지되어야 한다.
순서가 바뀌는 것을 우리의 가수 조영필씨가 매우 싫어한다. 즉, 1번 노래와 5번 노래를 같은 DVD에 녹화하기 위해서는
1번과 5번 사이의 모든 노래도 같은 DVD에 녹화해야 한다. 또한 한 노래를 쪼개서 두 개의 DVD에 녹화하면 안된다.
지니레코드 입장에서는 이 DVD가 팔릴 것인지 확신할 수 없기 때문에 이 사업에 낭비되는 DVD를 가급적 줄이려고 한다.
고민 끝에 지니레코드는 M개의 DVD에 모든 동영상을 녹화하기로 하였다. 이 때 DVD의 크기(녹화 가능한 길이)를 최소로 하려고 한다.
그리고 M개의 DVD는 모두 같은 크기여야 제조원가가 적게 들기 때문에 꼭 같은 크기로 해야 한다.

* 입력
첫째 줄에 자연수 N(1≤N≤1,000), M(1≤M≤N)이 주어진다.
다음 줄에는 조영필이 라이브에서 부른 순서대로 부른 곡의 길이가 분 단위로(자연수) 주어진다.
부른 곡의 길이는 10,000분을 넘지 않는다고 가정하자.

* 출력
첫 번째 줄부터 DVD의 최소 용량 크기를 출력하세요

🔍풀이
이진검색은 특정 값 사이에 반드시 찾는 값이 있다고 확신할 때 사용한다.

Arrays.stream(arr).max().getAsInt();

arr을 내부 반복자를 이용해 반복 탐색하여 가장 큰 값을 Int로 반환한다.
double이면 getAsDouble 등.

Arrays.stream(arr).sum();

arr의 합을 Int로 반환한다.

public int solution(int n, num, int[] arr){
	int answer = 0;
    //size값은 DVD에 한 곡만 담을 때 최솟값이고(lt)
    int lt = Arrays.stream(arr).max().getAsInt();
    //모든 곡을 DVD 한 장에 담을 때 최대값이다. (rt) 
    int rt = Arrays.stream(arr).sum();
    
   	while(lt <= rt){
    	int size = (lt/rt)/2;
        if(Count(size, arr) <= num){
        	// DVD장수에 여유가 있음 -> size를 더 줄일 수 있음
            //-> 더 큰 rt는 볼 필요가 없음
            rt = size - 1;
        	answer = size; 
        } else lt = size + 1; // 너무 줄였다 -> lt 키워줌 
    }
    return answer;
}
// DVD 장수 반환 매소드
public int Count(int size, int[] arr){
	int cnt = 1, sum = 0; // DVD 첫장
    for(int i : arr){
    	if(sum + i > size){
        //해당 장에는 다음 곡을 담을 용량이 없음
        cnt++; //다음장
        sum = i; //해당 곡 넣어준다.
        } else sum += i; //용량있으면 담아준다.
    }
    return cnt; //장수 반환 -> 허용된 장수 내에서 size가 가장 작은 경우 반환
  (더 줄이면 num을 넘어가는 지점까지)
}

✏️이분검색 문제2 (결정알고리즘)

* 설명
N개의 마구간이 수직선상에 있습니다. 각 마구간은 x1, x2, x3, ......, xN의 좌표를 가지며, 마구간간에 좌표가 중복되는 일은 없습니다.
현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 것을 좋아하지 않습니다. 각 마구간에는 한 마리의 말만 넣을 수 있고,
가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶습니다.
C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대값을 출력하는 프로그램을 작성하세요.

* 입력
첫 줄에 자연수 N(3<=N<=200,000)과 C(2<=C<=N)이 공백을 사이에 두고 주어집니다.
둘째 줄에 마구간의 좌표 xi(0<=xi<=1,000,000,000)가 차례로 주어집니다.


* 출력
첫 줄에 가장 가까운 두 말의 최대 거리를 출력하세요.

🔍풀이

public int solution(int n, int m, int[] arr){
	int answer = 0;
    Arrays.sort(arr);
    int lt = 1; //가능한 수 중 가장 작은 값 
    int rt = arr[n-1]; // 가장 큰 항
    while(rt >= lt){
    	int distance = (rt+lt)/2;
        if(Count(distance, arr) >= m){
        // 배치하는 말의 수 보다 크거나 같으면
        answer = distance;
        lt = distance+1; //배치 거리 늘리기
        else rt = distance-1; //배치수가 적은 경우 거리 줄이기
    	}    
 	}
    return answer;
}
public int Count(int distance, int[] arr){
	int cnt = 1, index = 0; //가장 첫번째에 배치했다고 가정
    for(int i = 0; i < arr.length; i++){
    	if(arr[i] - arr[index] >= distance){
        	// 배치가능한 거리가 된 경우
            cnt++;
            index = i; 
        }
    }
    return cnt;
}