Practice1 특정 값을 이진탐색으로 찾기
public class Practice1 {
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;
} else if (target < arr[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -left - 1;
}
public static void main(String[] args) {
// Test code
int[] arr = {1, 2, 5, 10, 20, 30, 40, 50, 60};
System.out.println(solution(arr, 30)); // 5
System.out.println(solution(arr, 3)); // -3
System.out.println(solution(arr, 11)); // -5
System.out.println(solution(arr, 35)); // -7
}
}-
배열 검증 : 먼저 입력된 배열이 null 이거나 길이 0인지 확인. 그렇다면 -1을 반환
-
이진 탐색 루프 while (left <= right) 루프에서 배열의 중간 위치를 계산하여 target 값과 비교
-target이 중간 값과 같다면, 해당 인덱스를 반환
-target이 중간 값보다 작으면 오른쪽 경계를 중간보다 왼쪽으로 이동
-target이 중간 값보다 크면 왼쪽 경계를 중간보다 오른쪽으로 이동 -
삽입 위치 변환 : 만약 값을 찾지 못하면, 삽입 위치를 나타내기 위해 -letf -1 을 반환. 이는 Arrays.binarySearch 메서드가 값을 찾지 못했을 때의 반환 방식과 유사
** 중간 인덱스 계산하는 두가지 방식
int mid = (left + right) / 2;
int mid2 = left + (right - left) / 2;
int a = Integer.MAX_VALUE;
int b = Integer.MAX_VALUE - 10;
int midAB = (a + b) / 2;
int midAB2 = a + (b - a) / 2;-
기본방식 : int mid = (left + right) / 2;
-가장 간단하고 직관적인 방식. left와 right 의 합을 2로 나누어 중간 인덱스를 계산 -
오버플로 방지 방식 : int mid2 = left + (right - left) / 2
-left와 right의 값이 매우 큰 경우에 사용됨. left 와 right 의 합이 int 범위를 초과할 때 오버플로가 발생할 수 있는데, 이를 방지하기 위해 (right - left)의 값을 사용하여 중간인덱스를 계산. 이 방식은 안전한 방식으로, 오버플로가 발생하지 않음
Practice2 회전배열에서 이진탐색
public class Practice2 {
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, 8, 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;
}
public static void main(String[] args) {
// Test code
int[] nums = {4, 5, 6, 7, 8, 0, 1, 2};
System.out.println(solution(nums, 0)); // 5
System.out.println(solution(nums, 3)); // -1
}
}-
초기화
-left 와 right 변수를 배열의 시작과 끝 인덱스로 초기화 -
이진 탐색 반복문
-반복문읜 left가 right보다 작거나 같은 동안 계속됨
-mid를 (left + right) / 2로 계산하여 중간 인덱스를 찾음 -
목표 값 비교
-target이 arr[mid]와 같으면 mid 를 반환 -
정렬된 절반 찾기
-배열의 좌측 절반이 정렬되어 있는지 확인 (arr[left] <= arr[mid]) : target 이 left 와 mid 사이에 있는지 확인하여 right 를 갱신하거나, 그렇지 않으면 left를 갱신
-배열의 우측 절반이 정렬되어 있는지 확인 : target 이 mid 와 right 사이에 있는지 확인하여 left 를 갱신하거나, 그렇지 않으면 right 를 갱신
Practice3 이차원 배열에서 이진탐색
public class Practice3 {
public static boolean solution(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0) {
return false;
}
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;
}
public static void main(String[] args) {
// Test code
int[][] matrix = {{1, 3, 7, 8}, {10, 11, 15, 20}, {21, 30, 35, 60}};
System.out.println(solution(matrix, 3)); // true
System.out.println(solution(matrix, 13)); // false
System.out.println(solution(matrix, 35)); // true
}
}-
초기화
-left 와 right 변수를 배열의 시작과 끝 인덱스로 초기화
-행(row) 의 갯수는 matrix.length로, 열(column) 의 갯수는 matrix[0].length 로 설정
-right 는 총 원소 수인 row * cols - 1; 로 설정 -
이진 탐색 반복문
-반복문은 left가 right 보다 작거나 같은 동안 계속됨
-mid 를 (left + right) / 2 로 계산하여 중간 인덱스를 찾음
-mid 를 이차원 인덱스로 변환하려면, mid / cols 는 행 인덱스, mid % cols 는 열 인덱스를 나타냄 -
목표값 비교
-target이 matrix[mid / cols][mid % cols] 와 같으면 true를 반환
-target이 중간 값보다 크면, left를 mid + 1 로 갱신
-target이 중간 값보다 작으면, right를 mid - 1 로 갱신 -
목표값이 없는 경우
-반복문이 종료되면 false를 반환
Practice4 weights 배열의 각 요소를 days 내에 배분하는 최적의 방법 찾기
public class Practice4 {
public static int solution(int[] weights, int days) {
int left = 0;
int right = 0;
for (int weight : weights) {
left = Math.max(left, weight);
right += weight;
}
while (left <= right) {
int mid = (left + right) / 2;
int cnt = 1;
int cur = 0;
for (int weight : weights) {
if (cur + weight > mid) {
cnt += 1;
cur = 0;
}
cur += weight;
}
if (cnt > days) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
public static void main(String[] args) {
// Test code
int[] weights = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
System.out.println(solution(weights, 5)); // 15
weights = new int[]{3, 2, 2, 4, 1, 4};
System.out.println(solution(weights, 3)); // 6
}
}문제설명
-입력 : 배열 weights 와 정수 days
-출력 : days 내에 모든 무게를 나눠서 운반할 때, 하루에 운반할 수 있는 최대 무게의 값
접근방법
-
초기화
-left는 weights 배열의 최대값(가장 큰 무게, 이는 최소한 하루에 운반해야 하는 무게의 하한)
-right는 weights 배열의 총 합(모든 무게를 하루에 운반하는 경우) -
이진탐색
-mid는 가능한 하루 최대 무게의 중간 값
-cnt는 mid 무게로 운반했을 때 필요한 일 수
-cur는 현재 날의 누적 무게
-cur + weight 가 mid를 초과하면 새로운 날로 넘어가고 cnt를 증가시킴 -
결과결정
-cnt가 days 보다 크면 mid 가 작아 하루에 운반할 수 있는 무게가 충분하지 않음. 따라서 left를 mid + 1 로 갱신
-그렇지 않으면 right를 mid - 1 로 갱신 -
반환
-이진탐색이 끝난 후 left가 원하는 결과를 갖게 됨
Practice5 nums 배열을 m개의 부분 배열로 나눌때, 각 부분 배열의 합 중 최대값이 최소가 되는 값을 찾기
public class Practice5 {
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;
}
public static void main(String[] args) {
// Test code
int[] nums = {7, 2, 5, 10, 8};
System.out.println(solution(nums, 2)); // 18
nums = new int[] {1, 2, 3, 4, 5};
System.out.println(solution(nums, 2)); // 9
nums = new int[] {1, 4, 4};
System.out.println(solution(nums, 3)); // 4
}
}문제설명
-입력 : 배열 nums와 정수 m
-출력 : 배열을 m 개의 부분 배열로 나누었을 때, 각 부분 배열의 합 중 최대값이 최소가 되는 값
접근방법
-
초기화
-left는 nums 배열의 최대값(각 부분 배열의 합 중 최대값의 하한)
-right는 nums 배열의 총 합(전체 배열을 하나의 부분 배열로 할 때 최대값) -
이진탐색
-mid는 가능한 각 부분 배열 합 중 최대값의 중간값
-cnt는 mid 값으로 배열을 나눌 때 필요한 부분 배열의 갯수
-total은 현재 부분 배열의 합 -
분배논리
-total에 현재 숫자를 더해 mid 를 초과하면 새로운 부분 배열로 시작
-이 때, cnt를 증가시키고, total을 현재 숫자로 초기화 -
결과 결정
-cnt가 m 이하이면 mid 가 클 가능성이 높으므로 right를 mid - 1로 갱신
-그렇지 않으면 left를 mid + 1 로 갱신 -
반환
-이진탐색이 끝난 후 left가 원하는 결과를 갖게 됨
