Binary Search

Median of two sorted arrays

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //merge these two arrays and find the median of the newly sorted array
        int arr[] = new int[nums1.length + nums2.length];

        sort(nums1,nums2,arr);
        return findMedian(arr);
    }
    public double findMedian(int arr[]){
        int mid = arr.length/2;
        if(arr.length %2!=0){

            return (double)arr[mid];
        }
        else{
            return (double)((double)(arr[mid]+arr[mid-1])/2);
        }
    }
    public void sort(int a[], int b[], int arr[]){
        int p = 0;
        int q = 0;
        int k =0;
        while(p<a.length && q < b.length){
            if(a[p]<b[q]){
                arr[k] = a[p++];
            }
            else{
                arr[k] = b[q++];
            }
            k++;
        }
        while(p<a.length){
            arr[k++] = a[p++];
        }
        while(q<b.length){
            arr[k++] = b[q++];
        }
    }
}

Allocate books

Explanation:

given :

Input: ‘n’ = 4 ‘m’ = 2
‘arr’ = [12, 34, 67, 90]

we are given list of books arr, where arr[i] has pages in the book i

we are given m students as well, we have to allocate books such that all the books are contiguously distributed among m students(same book is not assigned to two students)

now there can be a lot of contiguous distributions of the book

let say arr = [12, 34, 67, 90],and m = 2

We, will have two partitions of the arr

like 12|34,67,90 > student 1 will have 12 pages, student 2 will have 191 pages

or 12,34| 67,90 > student 1 will have 55 pages, student 2 will have 157 pages

or

12,34,67|90 > student 1 will have 113 pages, student 2 will have 90 pages

among all the distribution, maximum minimum no. of pages allocated is 113

Intuition:

We have to choose minimum no. of pages that a student can hold such that all the students get at least one book

In the given example the max page count is 90, this can be the min page that the student will have to hold ( else book with page 90 can not be held by any student)

now we will try to see if it is the maximum minimum no. of pages or not

[12, 34, 67, 90], students = 2

iteration 1 with 90:

for student 1

12+34<90 true, but 12+34+67 >90 hence student 1 will hold 12+34 = 46 pages

for student 2

67+90 > 90 hence student 2 will hold 67 pages

But there is one book with 90 pages remaining for this to be allocated we will need another student

This will increase the student count to 3, which is not possible

Hence the maximum minimum book can not be 90

We will try with Iteration 91,92,………MaxMinPage unless we find the max min page that can be used to assign all the book to all the 2 students that will be our answer

note: we can not go on forever …we will have to stop at some page count right, so the max page count will be sum(arr)

//for more details refer : https://youtu.be/Z0hwjftStI4?t=1412 for binary search
///brute force:
//tc: O(sum-max)*n
import java.util.*;
public class Solution {
    public static int findPages(ArrayList<Integer> arr, int n, int m) {
        if(m>n) return -1;

        // brute force
        int maximum = Integer.MIN_VALUE;
        int sum =0;
        for(int i : arr){
            maximum = Integer.max(i,maximum);
            sum+=i;
        }

        for(int max = maximum;max<=sum;max++){
            int student = allocate(max,arr);
            if(student ==m) return max;
        }
        return -1;
    }
    public static int allocate(int pages, ArrayList<Integer> arr){

        int student =0;
        int currentPagesForStudent =0;
        for(int i =0;i<arr.size();i++){

            if(currentPagesForStudent+arr.get(i)<=pages){
                currentPagesForStudent+=arr.get(i);
            }
            else{
                currentPagesForStudent = arr.get(i);
                student++;
            }
        }
        return student+1;

    }
}

///binary search://tc : O((log(sum-maximum-1)*(n)), where n is the arr.size()

import java.util.*;
public class Solution {
    public static int findPages(ArrayList<Integer> arr, int n, int m) {
        // book allocation impossible
        if (m > n)
            return -1;

        int low = Collections.max(arr);
        int high = arr.stream().mapToInt(Integer::intValue).sum();
        while (low <= high) {
            int mid = (low + high) / 2;
            int students = allocate(mid,arr);
            if (students > m) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return low;
    }
    public static int allocate(int pages, ArrayList<Integer> arr){

        int student =0;
        int currentPagesForStudent =0;
        for(int i =0;i<arr.size();i++){

            if(currentPagesForStudent+arr.get(i)<=pages){
                currentPagesForStudent+=arr.get(i);
            }
            else{
                currentPagesForStudent = arr.get(i);
                student++;
            }
        }
        return student+1;

    }
}

The above is the detailed content of Binary Search. For more information, please follow other related articles on the PHP Chinese website!