在兩個排序數組中找到丟失的數字

Question

我遇到了一個面試問題。給定兩個排序數組。
最初都設置了一組元素，但從一個數組中刪除了一個元素。
找到刪除的元素。
約束是我們必須在O（LOGN） 就地做到了對於回：

arr1[]={1,2,3,8,12,16}; 
arr2[]={1,2,8,12,16}; 

移除的元素是3

Answer 1

我從手機打字，所以它是一個僞代碼，但你會得到它：

take arr1.len/2.它是3.檢查arr1 [3]和arr2 [3]。如果它們相等，那麼缺少vsalue的索引大於3，否則小於3.這裏我們得到8和12。我們採取指數3/2 = 1。比較arr1 [1]和arr2 [1]。它們是相等的，所以在索引1和3之前缺失。所以它是arr1 [2] = 3。

這是主意。您正在進行二分查找，每次將searvh區域劃分一半。取決於比較，您可以將數組的左側或右側部分取出。你只需要實現這一點，並做一些檢查，但我認爲這個想法很明確。