Session9: Advance Binary Search

Original Session

Date: 17 Nov 2024

Topic: Advance Binary Search

1. Concept:

Programs

1. 1011. Capacity To Ship Packages Within D Days
   1. leetcode here

   public int shipWithinDays(int[] arr, int days) {
           
           int left = 0;
           int right = 0;
           for (int i=0;i<arr.length;i++) {
               
               if (arr[i] > left) {
                   left = arr[i];
               }
               right+=arr[i];
           }
   
           int ans = 0;
           while (left <= right) {
   
               int mid = (left + right)/2;
               int d = daysToShip(arr, mid);
               if (d <= days) {
                   right = mid - 1;
                   ans = mid;
                   
               } else {
                   left = mid + 1;
               }
               
           }
           return ans;
       }   
   
       int daysToShip(int[] arr, int capacity) {
   
           int sum = 0;
           int d = 1;
           for (int i=0;i<arr.length;i++) {
   
               if (sum + arr[i] <= capacity) {
                   sum += arr[i];
               } else {
                   d++;
                   sum = arr[i];
               }
           }
   
           return d;
       }

2. 875. Koko Eating Bananas
   1. leetcode here

   public int minEatingSpeed(int[] piles, int h) {
           
           int maxBanana = 0;
   
           for (int pile: piles) {
   
               if (pile > maxBanana) {
                   maxBanana = pile;
               }
           }
   
           int low = 1;
           int high = maxBanana;
           int ans = high;
   
           while (low <= high) {
   
               int mid = (low + high) / 2;
               if (fun(piles, h, mid)) {
                   ans = mid;
                   high = mid - 1;
               } else {
                   low = mid + 1;
               }
           }
   
           return ans;
       }
   
       boolean fun(int[] piles, int h, int capacity) {
   
               int hoursNeeded = 0;
   
               for (int pile: piles) {
   
                   hoursNeeded += Math.ceil((pile*1.0)/capacity);
               }
               return hoursNeeded<=h;
       }

3. 4. Median of Two Sorted Arrays
   1. leetcode here

   public double findMedianSortedArrays(int[] nums1, int[] nums2) {
   
           if (nums1.length > nums2.length) {
               return findMedianSortedArrays(nums2, nums1);
           }   
   
           int m = nums1.length;
           int n = nums2.length;
           int left = 0;
           int right = m;
   
           while (left <= right) {
   
               int partA = (left+right)/2;
               int partB = ((m+n+1)/2) - partA;
   
               int maxLeftA = (partA == 0)?Integer.MIN_VALUE:nums1[partA-1];
               int minRightA = (partA == m)?Integer.MAX_VALUE:nums1[partA];
   
               int maxLeftB = (partB == 0)?Integer.MIN_VALUE:nums2[partB-1];
               int minRightB = (partB == n)?Integer.MAX_VALUE:nums2[partB];
   
               if ((maxLeftA <= minRightB) &&
                   maxLeftB <= minRightA) {
                   
                   if ((m+n)%2 == 0) {
   
                       return (Math.max(maxLeftA, maxLeftB) + Math.min(minRightA, minRightB))/2.0;
                   } else {
   
                       return Math.max(maxLeftA, maxLeftB);
                   }
               } else if (maxLeftA > minRightB) {
   
                       right = partA - 1;
               } else {
   
                       left = partA + 1;
               }
           }
   
           return 0.0;
       }