[JAVA] 이진 탐색/이분 탐색

이진 탐색(Binary Search)

• 정렬된 배열에서 특정 값을 찾는 알고리즘
• 탐색 범위를 절반씩 줄여 나가기 때문에 선형탐색에 비해 빠른 속도 보장
• 시간 복잡도 O(logn) 상대적으로 매우 빠름

이때 선형 탐색이란?
- 배열(Array)이나 리스트(List)와 같은 데이터 구조에서 처음부터 끝까지 하나씩 값을 비교하면서 찾는 값을 찾을 때까지 탐색
- 즉, 정렬되지 않은 상태에서 찾는 것으로 이진탐색과 다른점시간 복잡도 O(n)

• 배열의 ‘중간 값’ 을 선택하여 찾고자 하는 값과 비교
• 만약 중간 값이 찾고자 하는 값보다 크면 ‘배열 왼쪽 부분’에서 탐색을 진행
  • 중간 값이 찾고자 하는 값보다 작으면 ‘배열 오른쪽 부분’에서 탐색을 진행
• 이 과정에서 찾고자 하는 값이 나올 때까지 반복

이진탐색 과정

정렬된 배열 array에서 key 값을 찾는 이진 탐색을 구현하는 과정

1. 탐색의 대상이 되는 자료들이 array[low]에서부터 array[high]에 들어있다고 가정하자. (즉, 정렬이 되어있어야함)
2. 즉, 어떤 시점에서 탐색되어야할 범위는 low ~ high까지가 된다.
3. 맨처음 low에는 0번 인덱스의 값, high에는 n-1번 인덱스의 값 들어간다.
4. low와 high 값에 의거해 중간값 mid 값은 (low + high)/2이다.
   1. 즉, array[low] ~ array[high]까지의 탐색은
   2. array[low] ~ array[middle-1] +  array[middle+1] + array[high]까지의 탐색
5. array[mid] 값과 구하고자 하는 key 값을 비교한다.
   1. key > mid
      1. 구하고자 하는 값이 중간값보다 높다면 low를 mid+1로 만들어 줌 (왼쪽 반을 버림)
   2. key < mid
      1. 구하고자 하는 값이 중간값보다 낮다면 high를 mid-1로 만들어 줌(오른쪽 반을 버림)
   3. key == mid
      1. 구하고자 하는 값을 찾음 중간값 리턴
6. low>high가 될 때까지 1~3번을 반복하면서 구하고자 하는 값을 찾는다.
   1. 이때까지 못 찾으면 탐색 실패 -1, false, error 등 리턴

 

순환 호출을 이용한 이진 탐색 구현

//시작 인덱스와 마지막 인덱스 값을 지정
int low = 0;
int high = array.length - 1;

int binarySearch1(int key, int low, int high) {
	int mid;
	
	if(low <= high) {
		mid = (low + high) / 2;
		
		if(key == arr[mid]) { 
			return mid; //탐색 성공
		} else if (key < arr[mid]) {
			//왼쪽 부분 arr[0] ~ arr[mid-1] 탐색
			return binarySearch1(key, low, mid - 1);
		} else {
			//오른쪽 부분 arr[mid+1] ~ arr[high] 탐색
			return binarySearch1(key, mid + 1, high);
		}
	}
	
	return -1; //탐색 실패
}

 

반복을 이용한 이진 탐색 구현

• 반복 구조를 사용하는 것이 재귀 호출로 구현하는 것보다 효율적이다.

//시작 인덱스와 마지막 인덱스 값을 지정
int low = 0;
int high = array.length - 1;

int binarySearch2(int key, int low, int high) {
	int mid;
	
	//높은 인덱스(high)가 낮은 인덱스(low)보다 크거나 같은지 확인
	while(low <= high) { 
		mid = (low + high) / 2;
		
		if(key == arr[mid]) {
			return mid;
		} else if(key < arr[mid]) {
			high = mid - 1;
		} else {
			low = mid + 1;
		}
	}
	
	return -1; //탐색 실패

 

이진 탐색의 문자열 탐색

• 문자열 배열의 경우 이진/이분 탐색을 사용하는 경우
  • Arrays.binarySearch() 함수를 이용하자!

Arrays.binarySearch()

• public static int binarySearch(Object[] a, Object key)
• 매개변수로 주어진 배열에서 원하는 값을 이진 탐색하여 인덱스를 반환 (int)
• 해당 원소가 배열에 없으면 음수를 반환
• 이진 탐색을 하기전 반드시 배열 정렬해야함

프로그래머스 [입국 심사]

https://school.programmers.co.kr/learn/courses/30/lessons/43238

프로그래머스

 

문제

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다.

 

가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다.

하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

 

입국심사를 기다리는 사람 수 n

각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times

모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return

 

입출력 예

n	times	return
6	[7, 10]	28

1. 가장 첫 두 사람은 바로 심사를 받으러 갑니다.
2. 7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다.
3. 10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다.
4. 14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다.
5. 20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않는다.
   1. 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.

 

풀이 과정

1. times의 배열의 최고 값을 기준으로 이분 탐색을 하면서
   1. mid 값으로 각 심사관이 몇명을 검색할 수 있냐만 계산해서 최솟값 구해보자
2. times를 오름차순으로 먼저 정렬
3. 시간의 최솟값, 최댓값 정하기
   1. min = 1 (1초)
   2. max = times[times.length - 1] * n
      1. 가장 느린 심사관(times[times.length -1])이 n명을 전부 심사하는 경우
4. 필요한 값 선언
   1. mid : 중간 값
   2. sum : 주어진 시간 mid 안에 총 몇명이 심사 받을 수 있는지 계산
   3. answer : 조건을 만족 하는 시간중 가장 짧은 시간을 저장
5. while문은 min ≤ max 일때
6. mid = (min + max) / 2;
   1. 현재 검사하고자 하는 시간
7. times 포문으로 sum을 계산해보기
   1. 각 심사관이 mid 시간동안 몇명을 심사할 수 있는지
   2. 그것의 합산 sum에 저장
8. sum이 n명 보다 크거나 같으면
   1. 최소 시간을 줄여서 더 탐색해보자 ! max = mid - 1
   2. 그치만 일단 저장하기 answer = mid

import java.util.*;
class Solution {
    public long solution(int n, int[] times) {
        Arrays.sort(times);
        long answer = 0;
        
        long min = 1;
        long max = (long)times[times.length-1]*n; //최장시간
        long mid;
        
        while (min <= max) {
            mid = (left + right)/2; //중간값
            
            long sum = 0; //중간값동안 탐색할 수 있는 총시간
            for(int time : times){
                sum += mid / time;
            }
            
            if(sum >= n){
                answer = mid;
                max = mid - 1;
            }else {
                min = mid + 1;
            }
            
        }
        return answer;
    }
}