在两个排序数组中找到丢失的数字

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区域划分一半。取决于比较，您可以将数组的左侧或右侧部分取出。你只需要实现这一点，并做一些检查，但我认为这个想法很明确。