p4.md

Problem

Given two sorted arrays and , design an algorithm to compute .

Idea

• 兩個排好的陣列中的元素相減的最小值
• 最小值先以兩陣列的第一個元素相減而得，之後若有更小值再取代之
• 因為是排好的陣列所以前面數不可能再大於後面比的數
• 所以比較過後須從較小數字所在的陣列找下一個數，才能有機會找到相減的更小值
• 其中若最小值為 0 ，直接跳出 while 迴圈

Solution

利用 while 迴圈（條件：i <= m && j <= n）。 先從 i = 1, j = 1 開始，將 x[i], y[j] 大的減小的存入 min。 再將小的移往下一個，例：若 x[i] < y[j]，i++。 做到結束，若出現小於 min 的數，則取代。 中間若出現 x[i] = y[j]，則 min = 0，直接跳出迴圈結束。

Analysis

每次跑 while 迴圈的時候，都會有 i 或 j 往上 +1 。所以最終 i = m, j = n 時，大約是 m+n 次。