# 從重復的數組中查找丟失的元素 > 原文： [https://www.geeksforgeeks.org/find-lost-element-from-a-duplicated-array/](https://www.geeksforgeeks.org/find-lost-element-from-a-duplicated-array/) 給定兩個數組，除了一個元素外，它們彼此重復，也就是說，其中一個元素丟失了，我們需要找到該元素。 **示例**： ``` Input: arr1[] = {1, 4, 5, 7, 9} arr2[] = {4, 5, 7, 9} Output: 1 1 is missing from second array. Input: arr1[] = {2, 3, 4, 5} arr2[] = {2, 3, 4, 5, 6} Output: 6 6 is missing from first array. ``` 一種**簡單解決方案**是遍歷數組并逐元素檢查元素，并在發現不匹配項時標記缺少的元素，但是此解決方案需要整個數組長度的線性時間。 另一種**有效解決方案**基于[二分搜索](http://geeksquiz.com/binary-search/)方法。 算法步驟如下： 1. 在更大的數組中開始二分搜索，并獲得（lo + hi）/ 2 的中間值 2. 如果兩個數組的值相同，則缺少的元素必須在右側，因此將 lo 設置為 mid 3. 否則將 hi 設置為 mid，因為如果 mid 元素不相等，則缺少的元素必須位于較大數組的左側。 4. 對于單元素和零元素數組，特殊情況將分別處理，單元素本身將是缺少的元素。 如果第一個元素本身不相等，則該元素將成為丟失的元素。/li> 以下是上述步驟 的實現 ## C++ ```cpp // C++ program to find missing element from same // arrays (except one missing element) #include <bits/stdc++.h> using namespace std; // Function to find missing element based on binary // search approach.? arr1[] is of larger size and // N is size of it.? arr1[] and arr2[] are assumed // to be in same order. int findMissingUtil(int arr1[], int arr2[], int N) { ????// special case, for only element which is ????// missing in second array ????if (N == 1) ????????return arr1[0]; ????// special case, for first element missing ????if (arr1[0] != arr2[0]) ????????return arr1[0]; ????// Initialize current corner points ????int lo = 0,? hi = N - 1; ????// loop until lo < hi ????while (lo < hi) ????{ ????????int mid = (lo + hi) / 2; ????????// If element at mid indices are equal ????????// then go to right subarray ????????if (arr1[mid] == arr2[mid]) ????????????lo = mid; ????????else ????????????hi = mid; ????????// if lo, hi becomes contiguous,? break ????????if (lo == hi - 1) ????????????break; ????} ????// missing element will be at hi index of ????// bigger array ????return arr1[hi]; } // This function mainly does basic error checking // and calls findMissingUtil void findMissing(int arr1[], int arr2[], int M, int N) { ????if (N == M-1) ????????cout << "Missing Element is " ????????<< findMissingUtil(arr1, arr2, M) << endl; ????else if (M == N-1) ????????cout << "Missing Element is " ????????<< findMissingUtil(arr2, arr1, N) << endl; ????else ????????cout << "Invalid Input"; } // Driver Code int main() { ????int arr1[] = {1, 4, 5, 7, 9}; ????int arr2[] = {4, 5, 7, 9}; ????int M = sizeof(arr1) / sizeof(int); ????int N = sizeof(arr2) / sizeof(int); ????findMissing(arr1, arr2, M, N); ????return 0; } ```