<p>Given two sorted arrays <code>nums1</code> and <code>nums2</code> of size <code>m</code> and <code>n</code> respectively, return <strong>the median</strong> of the two sorted arrays.</p>

<p>The overall run time complexity should be <code>O(log (m+n))</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums1 = [1,3], nums2 = [2]
<strong>Output:</strong> 2.00000
<strong>Explanation:</strong> merged array = [1,2,3] and median is 2.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums1 = [1,2], nums2 = [3,4]
<strong>Output:</strong> 2.50000
<strong>Explanation:</strong> merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>nums1.length == m</code></li>
	<li><code>nums2.length == n</code></li>
	<li><code>0 &lt;= m &lt;= 1000</code></li>
	<li><code>0 &lt;= n &lt;= 1000</code></li>
	<li><code>1 &lt;= m + n &lt;= 2000</code></li>
	<li><code>-10<sup>6</sup> &lt;= nums1[i], nums2[i] &lt;= 10<sup>6</sup></code></li>
</ul>

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<int>pendek = nums1; vector<int>panjang = nums2;
       
        if (panjang.size() < pendek.size()) swap(pendek,panjang);
        
        int sizePendek = pendek.size(), 
        sizePanjang = panjang.size(),
        total = sizePendek + sizePanjang, 
        half = total/2, 
        left = 0, 
        right = sizePendek - 1;
       
        while (true){  
            // midPendek ama midPanjang itu indexnya
            int midPendek = left+right < 0 ? -1 : (left+right)/2; 
            // [1,3] [2]
            // kalo misalnya left+right/2 doang
            // ada kondisi dimana
            // right = -1
            // left = 0
            // midPendek = 0 - 1 / 2 = 0 , tapi harusnya 0-1 / 2 = -0.5 buletin kebawah jadi -1 jadi midnya pindah gitu

            int midPanjang = half - (midPendek + 1) - 1;  // -1 karna index
            // midPendek + 1 -> jumlah angka sisi kiri
            // [1,2,3][4,5] 
            //  0 1 2  3 4
            //      m
            //  2 + 1 = 3 

            int leftPendek = midPendek >= 0 ? pendek[midPendek] : INT_MIN;
            int rightPendek = midPendek + 1 < sizePendek ? pendek[midPendek + 1] : INT_MAX;
            int leftPanjang = midPanjang >= 0 ? panjang[midPanjang] : INT_MIN;
            int rightPanjang = midPanjang + 1 < sizePanjang ? panjang[midPanjang + 1]: INT_MAX;

            if (leftPendek <= rightPanjang && leftPanjang <= rightPendek){
                if (total % 2 != 0) return min(rightPanjang, rightPendek);
                return ((double) max(leftPanjang, leftPendek) + min(rightPanjang, rightPendek)) / 2.0;
            }
        
            else if (leftPendek > rightPanjang) right = midPendek - 1;
            else left = midPendek + 1;

        }
    }

};

 // mental logic behind the ans
        // [1,1,2,2,3,3,4,4,5,5,6,7,8]
        // how do we find the median?
        // total = 13
        // karna total ganjil, kita membagi sisi kiri dan kanan secara seimbang trus kita ambil nilai yang tengah 
        // [1,1,2,2,3,3][4][4,5,5,6,7,8]
        //    6 angka         6 angka
        // median = 4

        // [1,1,2,2,3,3][4,4,5,5,6,7]
        // total = 12
        // karna total genap, kita tetap membagi sisi kiri dan kanan secara seimbang, tapi kita ambil nilai paling kanan atau besar
        // dari sisi kiri, dan ambil nilai paling kiri atau kecil dari sisi kanan kemudian jumlahkan trus bagi 2
        // nilai max kiri = 3
        // nilai min kanan = 4
        // median = 3+4 / 2 = 3.5

        // itu kalo array ny merge. kalo ga?    
        // test case 1 (ganjil)
        // [1,2,3,4,5,6,7,8] panjang
        // [1,2,3,4,5] pendek
        // total = 13
        // untuk cari median kita total/2 biar tau sisi kiri dan kanan ada berapa angka
        // half merged = 6 -> sisi kiri dan kanan array merged msing2 6 angka

        // kita cari dari array pendek sisi kiri dan kanan ada berapa angka
        // [1,2,3,4,5] pendek
        //  l   m   r

        // [1,2,3][4,5] 
        //  kiri  kanan

        //  sisi kiri array pendek = 3 angka
        //  sisi kiri array merged (half merged) = 6 angka
        //  maka,sisi kiri array panjang = 6 - 3 = 3 angka 

        // [1,2,3,4,5,6,7,8] panjang
        // [1,2,3][4,5,6,7,8]
        // tapi pembagian sisinya ini ud bener lom?
        // [1,2,3][4,5,6,7,8] array panjang ini ud kesorted jadi ud pasti bagian dari sisi kiri itu <= sisi kanan
        // tapi apakah elemen paling kanan sisi kiri dari array panjang ini <= elemen paling kiri sisi kanan array yang pendek? dan sebaliknya?
        // cek ini karena awalnya itu arraynya merged sehingga pembagian sisi nya ini harus tepat

        // [1,2,3] sisi kiri array panjang
        // [4,5] sisi kanan array pendek
        // elemen paling kanan sisi kiri <= elemen paling kiri sisi kanan 
        // bener

        // [1,2,3] sisi kiri array pendek
        // [4,5,6,7,8] sisi kanan array panjang
        // elemen paling kanan sisi kiri <= elemen paling kiri sisi kanan 
        // bener

        // karna 2 situasi ini benar maka untuk mengambil mediannya kita tinggal ambil nilai terkecil dari angka paling kiri sisi kanan kedua array
        // [4,5,6,7,8] sisi kanan array panjang
        // [4,5] sisi kanan array pendek 
        // median = min(4,4) = 4


        // testcase 2 (genap)
        // [1,2,3,4,5,6,7,8] panjang
        // [1,2,3,4] pendek
        // total = 12
        // half merged = 6
        // [1,2,3,4] pendek
        //  l m   r
        // [1,2][3,4]
        //  kiri kanan

        //  sisi kiri array pendek = 2 angka
        //  sisi kiri array merged (half merged) = 6 angka
        //  maka, sisi kiri array panjang = 6 - 2 = 4 angka 

        // [1,2,3,4,5,6,7,8] panjang
        // [1,2,3,4][5,6,7,8]
        //   kiri     kanan
        // bener ga ni? cek
        // [1,2,3,4] sisi kiri array panjang
        // [3,4] sisi kanan array pendek
        // elemen paling kanan sisi kiri <= elemen paling kiri sisi kanan 
        // salah // pembagian sisinya salah
        // harusnya abis 4 bukan 3
        // 
        
        // supaya bener geser pointernya
        // left = mid+1 , knp?
        // karna seperti yang tadi:
        // [1,2,3,4] sisi kiri 
        // [3,4] sisi kanan 
        // angka min disisi kanan itu  lebih kecil dari angka max dari sisi kiri
        // karna ini kesorting secara ascending maka kita geser ke kanan bro agar g dptin angka yang lebih kecil lagi
        //  [1,2,3,4] pendek
        //       l r
        //       m
        //  [1,2,3][4]
        //  kiri  kanan
        //  sisi kiri array pendek = 3 angka
        //  sisi kiri array merged (half merged) = 6 angka
        //  maka, sisi kiri array panjang = 6 - 3 = 3 angka 

        // [1,2,3,4,5,6,7,8] panjang
        // [1,2,3][4,5,6,7,8]
        //   kiri    kanan
        // cek bnr g ni

        // [1,2,3] sisi kiri array panjang
        // [4] sisi kanan array pendek
        // elemen paling kanan sisi kiri <= elemen paling kiri sisi kanan 
        // bener
        
        // [1,2,3] sisi kiri array pendek
        // [4,5,6,7,8] sisi kanan array panjang
        //  elemen paling kanan sisi kiri <= elemen paling kiri sisi kanan 
        // bener
        
        // karna 2 situasi ini benar kita bisa ambil mediannya
        // tapi karna totalnya genap maka kita ambil angka max dari kedua sisi kiri dan jumlahkan dengan angka min dari kedua sisi kanan
        // [1,2,3] sisi kiri array panjang
        // [1,2,3] sisi kiri array pendek
        // max(3,3) = 3

        // [4,5,6,7,8] sisi kanan array panjang
        // [4] sisi kanan array pendek
        // min(4,4) = 4
        // median = 3 + 4 / 2 = 3.5
        // done
95100