이진탐색(Binary Search)
이진탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수있는 알고리즘이다.
데이터가 무작위일때는 사용할 수없지만, 이지 정렬되어있다면 매우 빠르게 데이터를 찾을 수 있다는 특징이 있다.
이진탐색의 동작방식은 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있다.
이진탐색은 위치를 나타내는 변수 3개를 사용하는데 (1) 시작점 (2) 끝점 (3) 중간점 이다.
이진탐색의 아이디어는 간단하다. 정렬이 되어있다면 찾고자하는 수와 모든 수를 비교하며 찾을 필요없이
중간지점을 비교해서 찾고자 하는 값이 중간지점 값 보다 크면 (1) 중간 + 1 값부터 끝점 작다면 (2) 처음 부터 중간 - 1 값을 찾으면 되는데 이 범위에서 다시 중간지점을 찾고자 하는 수와 비교해서 값을 찾으면 되는 것이다.
그래서
- 이알고리즘의 시간 복잡도는 O(logN) 이다. 원소의 개수가 절반씩 줄어들기 때문이다.
코드를 보면 이진탐색이 간단하다고 생각이 들기 때문에 코드를 안외울수있다. 하지만 막상 구현해보려고 하면 어렵다.
유명작가 존 벤틀리 말에 따르면 제대로 이진 탐색 코드를 작성한 프로그래머는 10% 내외라고 할 정도로 구현은 까다롭다.
또한 이진 탐색은 코딩테스트에 단골로 나오는 문제이니 외우도록 하자.
재귀함수를 이용한 코드 :
import java.util.*;
public class Main {
// 이진 탐색 소스코드 구현(재귀 함수)
public static int binarySearch(int[] arr, int target, int start, int end) {
if (start > end) return -1;
int mid = (start + end) / 2;
// 찾은 경우 중간점 인덱스 반환
if (arr[mid] == target) return mid;
// 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
else if (arr[mid] > target) return binarySearch(arr, target, start, mid - 1);
// 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
else return binarySearch(arr, target, mid + 1, end);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 원소의 개수(n)와 찾고자 하는 값(target)을 입력받기
int n = sc.nextInt();
int target = sc.nextInt();
// 전체 원소 입력받기
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
// 이진 탐색 수행 결과 출력
int result = binarySearch(arr, target, 0, n - 1);
if (result == -1) {
System.out.println("원소가 존재하지 않습니다.");
}
else {
System.out.println(result + 1);
}
}
}반복문을 이용한 코트 :
import java.util.*;
public class Main {
// 이진 탐색 소스코드 구현(반복문)
public static int binarySearch(int[] arr, int target, int start, int end) {
while (start <= end) {
int mid = (start + end) / 2;
// 찾은 경우 중간점 인덱스 반환
if (arr[mid] == target) return mid;
// 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
else if (arr[mid] > target) end = mid - 1;
// 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
else start = mid + 1;
}
return -1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 원소의 개수(n)와 찾고자 하는 값(target)을 입력받기
int n = sc.nextInt();
int target = sc.nextInt();
// 전체 원소 입력받기
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
// 이진 탐색 수행 결과 출력
int result = binarySearch(arr, target, 0, n - 1);
if (result == -1) {
System.out.println("원소가 존재하지 않습니다.");
}
else {
System.out.println(result + 1);
}
}
}실전문제 1. 부품찾기
문제요약 :
전자 매장에는 부품이 N개 있고, 각 부품은 정수 형태의 고유한 번호가 있다. 부품 M개 종류가 모두 있는지 확인하는 프로그램을 작성해보자.
입력 예시
5
8 3 7 9 2
3
5 7 9
출력 예시
no yes yes
재귀함수를 이용한 구현코드 :
import java.util.*;
import java.io.*;
public class Main {
static int[] nn;
public static int binarySort(int start, int end, int target ) {
if(start > end) return -1;
int mid = (start + end) / 2;
if(nn[mid] == target) return mid;
else if(nn[mid] > target) { return binarySort(start ,mid - 1,target);}
else return binarySort(mid + 1 ,end, target);
}
public static void main(String[] args)throws IOException {
// TODO Auto-generated method stub
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
int n = Integer.parseInt(st.nextToken());
nn = new int[n];
st = new StringTokenizer(bf.readLine());
for(int i = 0 ; i < n ; i ++) {
nn[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(bf.readLine());
int m = Integer.parseInt(st.nextToken());
int[] mm = new int[m];
st = new StringTokenizer(bf.readLine());
for(int i = 0 ; i < m ; i ++) {
mm[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(nn);
for(int i = 0;i < m; i ++) {
if(binarySort(0 ,n-1, mm[i]) == -1){
System.out.print("no ");
}
else {
System.out.print("yes ");
}
}
}
}
반복문을 이용한 구현코드 :
import java.util.*;
import java.io.*;
public class Main {
static int[] nn;
public static int binarySort(int start, int end, int target ) {
while(start <= end) {
int mid = (start + end) / 2;
if(nn[mid] == target) return mid;
else if(nn[mid] > target) end = mid-1;
else start = mid+1;
}
return -1;
}
public static void main(String[] args)throws IOException {
// TODO Auto-generated method stub
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
int n = Integer.parseInt(st.nextToken());
nn = new int[n];
st = new StringTokenizer(bf.readLine());
for(int i = 0 ; i < n ; i ++) {
nn[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(bf.readLine());
int m = Integer.parseInt(st.nextToken());
int[] mm = new int[m];
st = new StringTokenizer(bf.readLine());
for(int i = 0 ; i < m ; i ++) {
mm[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(nn);
for(int i = 0;i < m; i ++) {
if(binarySort(0 ,n-1, mm[i]) == -1){
System.out.print("no ");
}
else {
System.out.print("yes ");
}
}
}
}
실천문제 2. 떡볶이 떡 만들기
문제요약 :
오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했습니다. 오늘은 떡볶이 떡을 만드는 날입니다.
동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않습니다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는
절단기로 잘라서 맞춰줍니다.
절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단합니다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고,
낮은 떡은 잘리지 않습니다. 예를 들어 높이가 19, 14, 10, 17cm 인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면
자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것입니다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm입니다.
손님은 6cm만큼의 길이를 가져갑니다.
손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의
최댓값을 구하는 프로그램을 작성하세요.
[입력 조건]
1. 첫째 줄에 떡의 개수 N과 요청한 떡의 길이 M이 주어집니다. (1 <= N <= 1,000,000, 1 <= M <= 2,000,000,000)
- 둘째 줄에는 떡의 개별 높이가 주어집니다. 떡 높이의 총합은 항상 M 이상이므로, 손님은 필요한 양만큼
떡을 사갈 수 있습니다. 높이는 10억보다 작거나 같은 양의 정수 또는 0 입니다.[출력 조건]
적어도 M만큼의 떡을 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값을 출력합니다.
<입력 예시>
4 6
19 15 10 17
<출력 예시>
15
재귀함수를 이용한 구현코드 :
import java.util.*;
import java.io.*;
public class Main9 {
static int[] nn;
static int n;
static int max;
public static int binarySort(int start, int end, int target) {
if(start > end ) return -1;
int mid = (start + end) / 2;
int sum = 0;
for(int i = 0 ; i < n ; i ++) {
if(nn[i] > mid) {
sum += (nn[i] - mid);
}
}
if(sum >= target) {
max = mid;
return binarySort(mid + 1, end ,target);
}else {
return binarySort(start, mid - 1 ,target);
}
}
public static void main(String[] args) throws IOException{
// TODO Auto-generated method stub
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
n = Integer.parseInt(st.nextToken());
nn = new int[n];
int m = Integer.parseInt(st.nextToken());
st = new StringTokenizer(bf.readLine());
for(int i = 0 ; i < n ; i ++) {
nn[i] = Integer.parseInt(st.nextToken());
}
int start = 0;
Arrays.sort(nn);
int end = nn[n-1];
int k = binarySort(start ,end, m);
System.out.println(max);
}
}
반복문을 이용한 구현코드 :
import java.util.*;
import java.io.*;
public class Main9 {
public static void main(String[] args) throws IOException{
// TODO Auto-generated method stub
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
int n = Integer.parseInt(st.nextToken());
int[] nn = new int[n];
int m = Integer.parseInt(st.nextToken());
st = new StringTokenizer(bf.readLine());
for(int i = 0 ; i < n ; i ++) {
nn[i] = Integer.parseInt(st.nextToken());
}
int start = 0;
Arrays.sort(nn);
int result = 0;
int end = nn[n-1];
while(start <= end) {
int mid = (start + end) /2;
int sum = 0;
for(int i = 0 ; i < n ; i ++) {
if(nn[i] > mid) {
sum += (nn[i] - mid);
}
}
if(sum >= m) {
result = mid;
start = mid + 1;
}else {
end = mid - 1;
}
}
System.out.println(result);
}
}
