In This below Java Program going to find the median of two sorted arrays using binary search approach.
In this program we are going to take two same size, sorted array array1 and array2 as input from user and find the median of the array obtained by merging these two arrays.
For example :- Taking following two array ‘array1′ and array2’, array1 = 10, 20, 30, 40, 45 array2 = 11, 15, 17, 18, 34 then Sorted (array1+array2) = 10, 11, 15, 17,18,20, 30,34, 40, 45 and therefore Median = (18 + 20) /2 => 19
Here Output should be return 19.
Java Program to Find the Median of two Sorted Arrays using Binary Search
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); System.out.println("How many number of elements do you want to enter in arrays"); int num = scan.nextInt(); int[] array1 = new int[ num ]; int[] array2 = new int[ num ]; System.out.println("Enter "+ num +" elements of array 1 in sorted order"); for (int j = 0; j < num; j++) array1[j] = scan.nextInt(); System.out.println("Enter "+ num +" elements of array 2 sorted order"); for (int i = 0; i < num; i++) array2[i] = scan.nextInt(); int median = median(array1, array2); System.out.println("Median of Sorted array is : = "+ median); } public static int median(int[] array1, int[] array2) { int length = array1.length; return findMedianSortedArrays(array1, 0, length -1 , array2, 0, length - 1); } public static int findMedianSortedArrays(int[] array1, int low1, int high1, int[] array2, int low2, int high2) { int middle1 = (high1 + low1 ) / 2; int middle2 = (high2 + low2 ) / 2; if (high1 - low1 == 1) return (Math.max(array1[low1] , array2[low2]) + Math.min(array1[high1] , array2[high2]))/2; else if (array1[middle1] > array2[middle2]) return findMedianSortedArrays(array1, low1, middle1 , array2, middle2 , high2); else return findMedianSortedArrays(array1, middle1 , high1, array2, low2 , middle2 ); } }
Output:- How many number of elements do you want to enter in arrays 5 How many number of elements do you want to enter in arrays 10 20 30 40 45 Enter 5 elements of array 2 sorted order 11 15 17 18 34 Median of Sorted array is : = 19