Day 14 of 100 Days of DSA Challenge: Searching Advanced
Tushar Pant
Advanced searching techniques push the boundaries of Binary Search, showcasing its adaptability for solving complex optimization problems. Today's tasks applied Binary Search to various challenging scenarios, emphasizing problem-solving strategies for efficient data searching and allocation.
1. Allocate Minimum Number of Pages
In this problem, books are allocated to students such that the maximum number of pages assigned to a student is minimized. Using Binary Search, the range of possible answers is narrowed based on a feasibility function that checks if the current allocation is valid within a given range.
import java.util.Scanner;
public class Main{
public static int allocateBooks(int[] books, int m) {
if (books.length < m) return -1;
int low = Integer.MIN_VALUE, high = 0;
for (int pages : books) {
low = Math.max(low, pages);
high += pages;
}
int result = high;
while (low <= high) {
int mid = low + (high - low) / 2;
if (isFeasible(books, m, mid)) {
result = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
return result;
}
private static boolean isFeasible(int[] books, int m, int maxPages) {
int students = 1, totalPages = 0;
for (int pages : books) {
if (totalPages + pages > maxPages) {
students++;
totalPages = pages;
if (students > m) return false;
} else {
totalPages += pages;
}
}
return true;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] books = {12, 34, 67, 90};
System.out.println("Pages per books are: ");
for(int i : books)
System.out.print(i+" ");
System.out.println();
System.out.print("Enter number of students: ");
System.out.println("Minimum maximum pages: " + allocateBooks(books, sc.nextInt()));
}
}
2. Minimum Capacity Required to Ship Packages Within D Days
This problem involves finding the minimum ship capacity required to deliver all packages within a given number of days. Binary Search is used to test capacities and refine the range based on the feasibility of shipping within d days.
import java.util.Scanner;
public class Main{
public static int shipWithinDays(int[] weights, int days) {
int maxWeight = 0, totalWeight = 0;
for (int weight : weights) {
maxWeight = Math.max(maxWeight, weight);
totalWeight += weight;
}
int left = maxWeight, right = totalWeight, result = totalWeight;
while (left <= right) {
int mid = left + (right - left) / 2;
if (isFeasible(weights, days, mid)) {
result = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return result;
}
private static boolean isFeasible(int[] weights, int days, int capacity) {
int daysRequired = 1, currentWeight = 0;
for (int weight : weights) {
if (currentWeight + weight > capacity) {
daysRequired++;
currentWeight = 0;
if (daysRequired > days) return false;
}
currentWeight += weight;
}
return true;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int[] weights = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
System.out.println("Weights are: ");
for(int i : weights)
System.out.print(i+" ");
System.out.println();
System.out.println("Enter number of Days: ");
int days = sc.nextInt();
System.out.println("Minimum capacity: " + shipWithinDays(weights, days));
}
}
3. Find the Smallest Missing Positive Integer
This problem finds the smallest positive integer missing from an unsorted array. Using techniques like partitioning and Binary Search on a modified array, the solution achieves O(n) complexity while using constant space.
import java.util.Arrays;
public class Main {
public static int findSmallestMissingPositive(int[] nums) {
System.out.println("Array: " + Arrays.toString(nums));
int n = nums.length;
for (int i = 0; i < n; i++) {
while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
int temp = nums[nums[i] - 1];
nums[nums[i] - 1] = nums[i];
nums[i] = temp;
}
}
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) return i + 1;
}
return n + 1;
}
public static void main(String[] args) {
int[] nums = {3, 4, -1, 1};
System.out.println("Smallest missing positive: " + findSmallestMissingPositive(nums));
}
}
4. Median of Two Sorted Arrays
Finding the median of two sorted arrays efficiently involves Binary Search over one of the arrays. By partitioning the arrays and checking conditions on the left and right halves, the solution guarantees O(log(min(n,m))) complexity for arrays of size n and m.
import java.util.Arrays;
public class Main{
public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
System.out.println("Array 1: " + Arrays.toString(nums1));
System.out.println("Array 2: " + Arrays.toString(nums2));
if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
int x = nums1.length, y = nums2.length;
int low = 0, high = x;
while (low <= high) {
int partitionX = (low + high) / 2;
int partitionY = (x + y + 1) / 2 - partitionX;
int maxX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];
int minX = (partitionX == x) ? Integer.MAX_VALUE : nums1[partitionX];
int maxY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];
int minY = (partitionY == y) ? Integer.MAX_VALUE : nums2[partitionY];
if (maxX <= minY && maxY <= minX) {
if ((x + y) % 2 == 0)
return (Math.max(maxX, maxY) + Math.min(minX, minY)) / 2.0;
else
return Math.max(maxX, maxY);
} else if (maxX > minY) {
high = partitionX - 1;
} else {
low = partitionX + 1;
}
}
throw new IllegalArgumentException();
}
public static void main(String[] args) {
int[] nums1 = {1, 3};
int[] nums2 = {2};
System.out.println("Median: " + findMedianSortedArrays(nums1, nums2));
}
}
5. Number of Times a Sorted Array Is Rotated
The problem involves finding the rotation count of a sorted array. Using Binary Search, the minimum element in the rotated array is located, and its index corresponds to the number of rotations. This is achieved in O(logn) time.
import java.util.Arrays;
public class Main{
public static int countRotations(int[] arr) {
System.out.println("Array: " + Arrays.toString(arr));
int low = 0, high = arr.length - 1;
while (low <= high) {
if (arr[low] <= arr[high]) return low;
int mid = low + (high - low) / 2;
int next = (mid + 1) % arr.length;
int prev = (mid + arr.length - 1) % arr.length;
if (arr[mid] <= arr[next] && arr[mid] <= arr[prev]) return mid;
else if (arr[mid] <= arr[high]) high = mid - 1;
else if (arr[mid] >= arr[low]) low = mid + 1;
}
return -1;
}
public static void main(String[] args) {
int[] arr = {15, 18, 2, 3, 6, 12};
System.out.println("Number of rotations: " + countRotations(arr));
}
}
Reflection
Day 14 highlighted Binary Search as an optimization tool for diverse problem domains, from array manipulations to resource allocation. Each problem illustrated the importance of customizing Binary Search for specific constraints, underscoring its flexibility and efficiency in advanced scenarios. 🚀
Subscribe to my newsletter
Read articles from Tushar Pant directly inside your inbox. Subscribe to the newsletter, and don't miss out.
Written by