{"id":2683,"date":"2021-10-14T12:15:00","date_gmt":"2021-10-14T06:45:00","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=2683"},"modified":"2021-10-21T11:59:16","modified_gmt":"2021-10-21T06:29:16","slug":"median-of-two-sorted-arrays","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/median-of-two-sorted-arrays\/","title":{"rendered":"Median of Two Sorted Arrays"},"content":{"rendered":"\n<div class=\"gutentoc tocactive nostyle\" style=\"max-width:400px\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"toggletwo\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#simple-approach-using-extra-space\">Simple approach: Using Extra Space<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation\">C++ Implementation<\/a><\/li><li><a href=\"#-java-implementation\"><meta charset=\"utf-8\">Java Implementation<\/a><\/li><li><a href=\"#-python-implementation\"><meta charset=\"utf-8\">Python Implementation<\/a><\/li><\/ul><li><a href=\"#efficient-approach-using-binary-search\">Efficient Approach (Using binary search)<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code-for-binary-search-approach\">C++ Code for Binary Search Approach<\/a><\/li><li><a href=\"#-java-code-for-binary-search-approach\"><meta charset=\"utf-8\">Java Code for Binary Search Approach<\/a><\/li><li><a href=\"#-python-code-for-binary-search-approach\"><meta charset=\"utf-8\">Python Code for Binary Search Approach<\/a><\/li><\/ul><li><a href=\"#practice-question\">Practice Question<\/a><\/li><li><a href=\"#frequently-asked-questions\">Frequently Asked Questions<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>There are two sorted arrays <strong>A<\/strong> and <strong>B<\/strong> of sizes <strong>m<\/strong> and <strong>n<\/strong> respectively.<\/p>\n\n\n\n<p>Find the median of the two sorted arrays( The median of the array formed by merging both the arrays).<\/p>\n\n\n\n<p>Median: The middle element is found by ordering all elements in sorted order and picking out the one in the middle (or if there are two middle numbers, taking the mean of those two numbers).<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"358\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Median 1\"  class=\"wp-image-2776 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-5-1024x358.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-5-1024x358.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-5-300x105.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-5-768x269.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-5-380x133.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-5-550x192.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-5-800x280.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-5.png 1066w\" ><\/figure><\/div>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"231\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Median 2\"  class=\"wp-image-2782 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-11-1024x231.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-11-1024x231.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-11-300x68.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-11-768x173.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-11-380x86.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-11-550x124.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-11-800x180.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-11.png 1066w\" ><\/figure><\/div>\n\n\n\n<p><strong>Examples:<\/strong><\/p>\n\n\n\n<p><strong>Input:&nbsp; <\/strong>A[] = {1, 4, 5}, B[] = {2, 3}<br><strong>Output: <\/strong>3<br><strong>Explanation:<\/strong><br>Merging both the arrays and arranging in ascending:<br>[1, 2, 3, 4, 5]<br>Hence, the median is 3<\/p>\n\n\n\n<p><strong>Input: <\/strong>A[] = {1, 2, 3, 4}, B[] = {5, 6}<br><strong>Output:<\/strong> 3.5<br><strong>Explanation:<br><\/strong>Union of both arrays:<br>{1, 2, 3, 4, 5, 6}<br>Median = (3 + 4) \/ 2 = 3.5<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"simple-approach-using-extra-space\">Simple approach: Using Extra Space<\/h2>\n\n\n\n<p>The most basic approach is to merge both the sorted arrays using an auxiliary array. The median would be the middle element in the case of an odd-length array or the mean of both middle elements in the case of even length array.<br>The merging of two sorted arrays is similar to the algorithm which we follow in <strong>merge sort<\/strong>.<\/p>\n\n\n\n<p><strong>Algorithm<\/strong><\/p>\n\n\n\n<ul><li>The first element of both lists is compared.&nbsp;<\/li><li>If sorted in ascending order, the smaller element among two becomes a new element of the sorted list.&nbsp;<\/li><li>This procedure is repeated until both the smaller sublists are empty and the newly combined sublist covers all the elements of both the sublists.<\/li><li>Maintain a variable <strong>count<\/strong> for the output array and if count equals <strong>(N + M) \/ 2<\/strong>, then it is the median of the odd length array and if it is even, store the mean of <strong>(N + M) \/ 2th <\/strong>and <strong>(N + M) \/ 2 &#8211; 1 <\/strong>th element.<\/li><\/ul>\n\n\n\n<h3 id=\"c-implementation\">C++ Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int getMedian(int A[], int B[], int n, int m)\n{\n    int i = 0;\n    int j = 0;\n    int count;\n    int m1 = -1, m2 = -1;\n \n    if((m + n) % 2 == 1)\n    {\n        for (count = 0; count &lt;= (n + m)\/2; count++)\n        {\n            if(i != n &amp;&amp; j != m)\n            {\n                m1 = (A[i] > B[j]) ? B[j++] : A[i++];\n            }\n            else if(i &lt; n)\n            {\n                m1 = A[i++];\n            }\n            else\n            {\n                m1 = B[j++];\n            }\n        }\n        return m1;\n    }\n    else\n    {\n        for (count = 0; count &lt;= (n + m)\/2; count++)\n        {\n            m2 = m1;\n            if(i != n &amp;&amp; j != m)\n            {\n                m1 = (A[i] > B[j]) ? B[j++] : A[i++];\n            }\n            else if(i &lt; n)\n            {\n                m1 = A[i++];\n            }\n            else\n            {\n                m1 = B[j++];\n            }\n        }\n        return (m1 + m2)\/2;\n    }\n}<\/pre>\n\n\n\n<p>Practice on our\u00a0<a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/online-cpp-compiler\/\" target=\"_blank\">C++ Compiler<\/a><\/p>\n\n\n\n<h3 id=\"-java-implementation\"><span id=\"java-implementation\"><meta charset=\"utf-8\">Java Implementation<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">static int getMedian(int A[], int B[],\n                     int n, int m)\n{\n    int i = 0;\n    int j = 0;\n    int count;\n    int m1 = -1, m2 = -1;\n     \n    if ((m + n) % 2 == 1)\n    {\n        for(count = 0;\n            count &lt;= (n + m) \/ 2;\n            count++)\n        {\n            if (i != n &amp;&amp; j != m)\n            {\n                m1 = (A[i] > B[j]) ?\n                      B[j++] : A[i++];\n            }\n            else if (i &lt; n)\n            {\n                m1 = A[i++];\n\t\t\t}\n            else\n            {\n                m1 = B[j++];\n            }\n        }\n        return m1;\n    }\n    else\n    {\n        for(count = 0;\n            count &lt;= (n + m) \/ 2;\n            count++)\n        {\n            m2 = m1;\n            if (i != n &amp;&amp; j != m)\n            {\n                m1 = (A[i] > B[j]) ?\n                      B[j++] : A[i++];\n            }\n            else if (i &lt; n)\n            {\n                m1 = A[i++];\n            }\n            else\n            {\n                m1 = B[j++];\n            }\n        }\n        return (m1 + m2) \/ 2;\n    }\n}<\/pre>\n\n\n\n<p>Practice on our\u00a0<a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/online-java-compiler\/\" target=\"_blank\">Java Compiler<\/a><\/p>\n\n\n\n<h3 id=\"-python-implementation\"><span id=\"python-implementation\"><meta charset=\"utf-8\">Python Implementation<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def getMedian(A, B, n, m) :\n \n    i = 0 \n    j = 0 \n    m1, m2 = -1, -1\n \n    if((m + n) % 2 == 1) :   \n        for count in range(((n + m) \/\/ 2) + 1) :       \n            if(i != n and j != m) :           \n                if A[i] > B[j] :\n                    m1 = B[j]\n                    j += 1\n                else :\n                    m1 = A[i]\n                    i += 1           \n            elif(i &lt; n) :           \n                m1 = A[i]\n                i += 1\n          \n            # for case when j&lt;m,\n            else :           \n                m1 = B[j]\n                j += 1       \n        return m1\n     \n    else :\n        for count in range(((n + m) \/\/ 2) + 1) :        \n            m2 = m1\n            if(i != n and j != m) :       \n                if A[i] > B[j] :\n                    m1 = B[j]\n                    j += 1\n                else :\n                    m1 = A[i]\n                    i += 1           \n            elif(i &lt; n) :           \n                m1 = A[i]\n                i += 1\n             \n            # for case when j&lt;m,\n            else :           \n                m1 = B[j]\n                j += 1       \n        return (m1 + m2)\/\/2<\/pre>\n\n\n\n<p>Practice on our\u00a0<a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/online-python-compiler\/\" target=\"_blank\">Python Compiler<\/a><\/p>\n\n\n\n<div class=\"wp-container-1 wp-block-buttons\"><\/div>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(N + M) where N and M is the size of the array <strong>A[]<\/strong> and <strong>B[]Space Complexity:<\/strong> O(1)<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"efficient-approach-using-binary-search\">Efficient Approach (Using binary search)<\/h2>\n\n\n\n<p>The key idea to note here is that both the arrays are <strong>sorted<\/strong>. Therefore, this leads us to think of <strong>binary search<\/strong>.&nbsp; Let us try to understand the algorithm using an example:<\/p>\n\n\n\n<p><strong>A[]<\/strong> = {1, 4, 7}<br><strong>B[]<\/strong> = {2, 3, 5, 6}<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full\"><img  loading=\"lazy\"  width=\"885\"  height=\"728\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Median of Two Sorted Array Binary Search\"  class=\"wp-image-2774 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 885px) 100vw, 885px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-3.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-3.png 885w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-3-300x247.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-3-768x632.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-3-380x313.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-3-550x452.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-3-800x658.png 800w\" ><\/figure><\/div>\n\n\n\n<p>From the above diagram, it can be easily deduced that only the <strong>first half<\/strong> of the array is needed and the <strong>right half<\/strong> can be discarded.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"885\"  height=\"590\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"First Half Median\"  class=\"wp-image-2777 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 885px) 100vw, 885px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-6.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-6.png 885w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-6-300x200.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-6-768x512.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-6-380x253.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-6-550x367.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-6-800x533.png 800w\" ><\/figure>\n\n\n\n<p>Similarly, for an even length merged array, ignore the <strong>right half<\/strong> and only the <strong>left half<\/strong> contributes to our final answer.<\/p>\n\n\n\n<p>Therefore, the motive of our approach is to find which of the elements from both the array helps in contributing to the final answer. Therefore, the <strong>binary search <\/strong>comes to the rescue, as it can discard a part of the array every time, the elements don\u2019t contribute to the median.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"885\"  height=\"728\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Binary Search Approach 1\"  class=\"wp-image-2773 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 885px) 100vw, 885px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-2.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-2.png 885w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-2-300x247.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-2-768x632.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-2-380x313.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-2-550x452.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-2-800x658.png 800w\" ><\/figure>\n\n\n\n<p><strong>Algorithm<\/strong><\/p>\n\n\n\n<ul><li>The first array is of size <strong>n<\/strong>, hence it can be split into <strong>n + 1 <\/strong>parts.<\/li><li>The second array is of size <strong>m<\/strong>, hence it can be split into <strong>m + 1 <\/strong>parts<\/li><\/ul>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"723\"  height=\"212\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"i + 1 \"  class=\"wp-image-2780 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 723px) 100vw, 723px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-9.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-9.png 723w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-9-300x88.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-9-380x111.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-9-550x161.png 550w\" ><\/figure>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"723\"  height=\"212\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-2778 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 723px) 100vw, 723px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-7.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-7.png 723w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-7-300x88.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-7-380x111.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-7-550x161.png 550w\" ><\/figure>\n\n\n\n<ul><li>As discussed earlier, we just need to find the elements contributing to the left half of the array.<ul><li>Since, the arrays are already sorted, it can be deduced that <strong>A[i &#8211; 1] &lt; A[i] <\/strong>and <strong>B[i &#8211; 1] &lt; B[i]<\/strong>.<\/li><li>Therefore, we just need to find the index <strong>i<\/strong>, such that <strong>A[i &#8211; 1] &lt;= B[j] <\/strong>and <strong>B[j &#8211; 1] &lt;= A[i].<\/strong><\/li><\/ul><\/li><\/ul>\n\n\n\n<ul><li>Consider <strong>mid = (n + m &#8211; 1) \/&nbsp; 2 <\/strong>and check if this satisfies the above condition.<ul><li>If <strong>A[i-1] &lt;= B[j]<\/strong> and <strong>B[j-1]&lt;=A[i]<\/strong> satisfies the condition, return the index <strong>i<\/strong>.<\/li><li>If <strong>A[i] &lt; B[j &#8211; 1]<\/strong>, increase the range towards the right. Hence update <strong>i =&nbsp; mid + 1<\/strong>.<\/li><li>Similarly, if <strong>A[i &#8211; 1] &gt; B[j]<\/strong>, decrease the range towards left. Hence update <strong>i =&nbsp; mid &#8211; 1<\/strong>.<\/li><\/ul><\/li><\/ul>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"827\"  height=\"268\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-2775 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 827px) 100vw, 827px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-4.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-4.png 827w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-4-300x97.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-4-768x249.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-4-380x123.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-4-550x178.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-4-800x259.png 800w\" ><\/figure>\n\n\n\n<p><strong>i<\/strong> is the mid of array <strong>A<\/strong> as shown below:<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"827\"  height=\"297\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-2779 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 827px) 100vw, 827px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-8.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-8.png 827w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-8-300x108.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-8-768x276.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-8-380x136.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-8-550x198.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-8-800x287.png 800w\" ><\/figure>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"885\"  height=\"546\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-2772 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 885px) 100vw, 885px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-1.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-1.png 885w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-1-300x185.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-1-768x474.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-1-380x234.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-1-550x339.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-1-800x494.png 800w\" ><\/figure>\n\n\n\n<ul><li>Few corner cases to take care of :<\/li><li>If the size of any of the arrays is <strong>0<\/strong>, return the median of the non-zero sized array.<\/li><li>If the size of smaller array is <strong>1<\/strong>,:<ul><li>If the size of the larger array is also&nbsp; one, simply return the median as the mean of both the elements.<\/li><li>Else, if size of larger array is odd, adding the element from first array will result in size even, hence median will be affected if and only if, the element of the first array lies between <strong>, M \/ 2th<\/strong> and <strong>M\/2 + 1<\/strong>th element of <strong>B[].<\/strong><\/li><li>Similarly, if the size of the larger array is even, check for the element of the smaller array, <strong>M\/2th element <\/strong>and <strong>M \/ 2 + 1 th <\/strong>element.<\/li><\/ul><\/li><\/ul>\n\n\n\n<ul><li>If the size of smaller array is <strong>2<\/strong>,<ul><li>If a larger array has an odd number of elements, the median can be either the <strong>middle<\/strong> element<strong> or <\/strong>the median of elements of smaller array and <strong>M\/2 -1th <\/strong>element or minimum of the second element of <strong>A[]<\/strong> and <strong>M\/2+ 1<\/strong> th array.<\/li><\/ul><\/li><\/ul>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full\"><img  loading=\"lazy\"  width=\"885\"  height=\"728\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-2781 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 885px) 100vw, 885px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-10.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-10.png 885w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-10-300x247.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-10-768x632.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-10-380x313.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-10-550x452.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Median-of-Two-Sorted-Array-Image-10-800x658.png 800w\" ><\/figure><\/div>\n\n\n\n<h3 id=\"c-code-for-binary-search-approach\">C++ Code for Binary Search Approach<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">float MO2(int a, int b)\n{ return ( a + b ) \/ 2.0; }\n \nfloat MO3(int a, int b, int c)\n{\n    return a + b + c - max(a, max(b, c))\n                     - min(a, min(b, c));\n}\n \nfloat MO4(int a, int b, int c, int d)\n{\n    int Max = max( a, max( b, max( c, d ) ) );\n    int Min = min( a, min( b, min( c, d ) ) );\n    return ( a + b + c + d - Max - Min ) \/ 2.0;\n}\n \nfloat medianSingle(int arr[], int n)\n{\n   if (n == 0)\n      return -1;\n   if (n%2 == 0)\n        return (double)(arr[n\/2] + arr[n\/2-1])\/2;\n   return arr[n\/2];\n}\nfloat findMedianUtil( int A[], int N, int B[], int M )\n{\n    if (N == 0)\n      return medianSingle(B, M);\n \n    if (N == 1)\n    {\n        if (M == 1)\n            return MO2(A[0], B[0]);\n \n        if (M &amp; 1)\n            return MO2( B[M\/2], MO3(A[0], B[M\/2 - 1], B[M\/2 + 1]) );\n \n        return MO3( B[M\/2], B[M\/2 - 1], A[0] );\n    }\n    else if (N == 2)\n    {\n        if (M == 2)\n            return MO4(A[0], A[1], B[0], B[1]);\n \n        if (M &amp; 1)\n            return MO3 ( B[M\/2],\n                         max(A[0], B[M\/2 - 1]),\n                         min(A[1], B[M\/2 + 1])\n                       );\n \n        return MO4 ( B[M\/2],\n                     B[M\/2 - 1],\n                     max( A[0], B[M\/2 - 2] ),\n                     min( A[1], B[M\/2 + 1] )\n                   );\n    }\n \n    int idxA = ( N - 1 ) \/ 2;\n    int idxB = ( M - 1 ) \/ 2;\n \n    if (A[idxA] &lt;= B[idxB] )\n      return findMedianUtil(A + idxA, N\/2 + 1, B, M - idxA );\n \n    return findMedianUtil(A, N\/2 + 1, B + idxA, M - idxA );\n}\nfloat findMedian( int A[], int N, int B[], int M )\n{\n    if (N > M)\n       return findMedianUtil( B, M, A, N );\n \n    return findMedianUtil( A, N, B, M );\n}<\/pre>\n\n\n\n<h3 id=\"-java-code-for-binary-search-approach\"><span id=\"java-code-for-binary-search-approach\"><meta charset=\"utf-8\">Java Code for Binary Search Approach<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">static float MO2(int a, int b) {\n        return (float) ((a + b) \/ 2.0);\n    }\n \n    static float MO3(int a, int b, int c) {\n        return a + b + c - Math.max(a, Math.max(b, c)) -\n          Math.min(a, Math.min(b, c));\n    }\n    static float MO4(int a, int b, int c, int d) {\n        int Max = Math.max(a, Math.max(b, Math.max(c, d)));\n        int Min = Math.min(a, Math.min(b, Math.min(c, d)));\n        return (float) ((a + b + c + d - Max - Min) \/ 2.0);\n    }\n    static float medianSingle(int arr[], int n) {\n        if (n == 0)\n            return -1;\n        if (n % 2 == 0)\n            return (float) ((double) (arr[n \/ 2] +\n                                      arr[n \/ 2 - 1]) \/ 2);\n        return arr[n \/ 2];\n    }\n    static float findMedianUtil(int A[], int N, int B[], int M) {\n        if (N == 0)\n            return medianSingle(B, M);\n \n        if (N == 1) {\n            if (M == 1)\n                return MO2(A[0], B[0]);\n \n            if (M % 2 == 1)\n                return MO2(B[M \/ 2], (int) MO3(A[0],\n                            B[M \/ 2 - 1], B[M \/ 2 + 1]));\n \n            return MO3(B[M \/ 2], B[M \/ 2 - 1], A[0]);\n        }\n        else if (N == 2) {\n            if (M == 2)\n                return MO4(A[0], A[1], B[0], B[1]);\n \n            \n            if (M % 2 == 1)\n                return MO3(B[M \/ 2], Math.max(A[0], B[M \/ 2 - 1]),\n                           Math.min(A[1], B[M \/ 2 + 1]));\n \n            \n            return MO4(B[M \/ 2], B[M \/ 2 - 1],\n                       Math.max(A[0], B[M \/ 2 - 2]),\n                       Math.min(A[1], B[M \/ 2 + 1]));\n        }\n \n        int idxA = (N - 1) \/ 2;\n        int idxB = (M - 1) \/ 2;\n        if (A[idxA] &lt;= B[idxB])\n            return findMedianUtil(Arrays.copyOfRange(A, idxA, A.length),\n                                  N \/ 2 + 1, B, M - idxA);\n \n       \n        return findMedianUtil(A, N \/ 2 + 1,\n               Arrays.copyOfRange(B, idxB, B.length), M - idxA);\n    }\n    static float findMedian(int A[], int N, int B[], int M)\n    {\n        if (N > M)\n            return findMedianUtil(B, M, A, N);\n \n        return findMedianUtil(A, N, B, M);\n    }<\/pre>\n\n\n\n<h3 id=\"-python-code-for-binary-search-approach\"><span id=\"python-code-for-binary-search-approach\"><meta charset=\"utf-8\">Python Code for Binary Search Approach<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def MO2(a, b) :\n    return ( a + b ) \/ 2\n \ndef MO3(a, b, c) :\n \n    return a + b + c - max(a, max(b, c)) - min(a, min(b, c))\n \ndef MO4(a, b, c, d) :\n    Max = max( a, max( b, max( c, d ) ) )\n    Min = min( a, min( b, min( c, d ) ) )\n    return ( a + b + c + d - Max - Min ) \/ 2\n \ndef medianSingle(arr, n) :\n    if (n == 0) :\n        return -1\n    if (n % 2 == 0) :\n            return (arr[n \/ 2] + arr[n \/ 2 - 1]) \/ 2\n    return arr[n \/ 2]\n \ndef findMedianUtil(A, N, B, M) :\n \n    if (N == 0) :\n        return medianSingle(B, M)\n \n    if (N == 1) :\n        if (M == 1) :\n            return MO2(A[0], B[0])\n \n        if (M &amp; 1 != 0) :\n            return MO2( B[M \/ 2], MO3(A[0], B[M \/ 2 - 1], B[M \/ 2 + 1]) )\n \n        return MO3(B[M \/\/ 2], B[M \/\/ 2 - 1], A[0])\n \n    elif (N == 2) :\n        if (M == 2) :\n            return MO4(A[0], A[1], B[0], B[1])\n \n        if (M &amp; 1 != 0) :\n            return MO3 (B[M \/ 2], max(A[0], B[M \/ 2 - 1]), min(A[1], B[M \/ 2 + 1]))\n \n        return MO4 (B[M \/ 2], B[M \/ 2 - 1], max( A[0], B[M \/ 2 - 2] ), min( A[1], B[M \/ 2 + 1] ))\n \n    idxA = ( N - 1 ) \/ 2\n    idxB = ( M - 1 ) \/ 2\n \n    if (A[idxA] &lt;= B[idxB] ) :\n        return findMedianUtil(A + idxA, N \/ 2 + 1, B, M - idxA )\n \n    return findMedianUtil(A, N \/ 2 + 1, B + idxA, M - idxA )\n \ndef findMedian(A, N, B, M) :\n \n    if (N > M) :\n        return findMedianUtil( B, M, A, N );\n    return findMedianUtil( A, N, B, M )<\/pre>\n\n\n\n<p><strong>Time Complexity: <\/strong>O(log(min(N,M)) where N and M is the size of the array <strong>A[]<\/strong> and <strong>B[].Space Complexity: <\/strong>O(1), as no extra space is used.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"practice-question\">Practice Question<\/h2>\n\n\n\n<p id=\"median-of-array\"><a href=\"https:\/\/www.interviewbit.com\/problems\/median-of-array\/\" target=\"_blank\" rel=\"noreferrer noopener\">Median of Array<\/a><\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"frequently-asked-questions\">Frequently Asked Questions<\/h2>\n\n\n\n<p><strong>Do the arrays need to be sorted?<br><\/strong>Yes, both the arrays need, else you cannot apply the binary search technique to find the median.<br><\/p>\n\n\n\n<p><strong>What is the median of an array?<br><\/strong>The middle element is found by ordering all elements in sorted order and picking out the one in the middle (or if there are two middle numbers, taking the mean of those two numbers).<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement There are two sorted arrays A and B of sizes m and n respectively. Find the&hellip;\n","protected":false},"author":5,"featured_media":2783,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[144,458,462],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2683"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=2683"}],"version-history":[{"count":5,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2683\/revisions"}],"predecessor-version":[{"id":24094,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2683\/revisions\/24094"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/2783"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=2683"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=2683"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=2683"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}