Find lost element from a duplicated array | 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 . ; special case , for only element which is missing in second array ; special case , for first element missing ; Initialize current corner points ; loop until lo < hi ; If element at mid indices are equal then go to right subarray ; if lo , hi becomes contiguous , break ; missing element will be at hi index of bigger array ; This function mainly does basic error checking and calls findMissingUtil ; Driver Code
function findMissingUtil ( arr1 , arr2 , N ) { if ( N == 1 ) return arr1 [ 0 ] ; if ( arr1 [ 0 ] != arr2 [ 0 ] ) return arr1 [ 0 ] ; let lo = 0 , hi = N - 1 ; while ( lo < hi ) { let mid = parseInt ( ( lo + hi ) / 2 , 10 ) ; if ( arr1 [ mid ] == arr2 [ mid ] ) lo = mid ; else hi = mid ; if ( lo == hi - 1 ) break ; } return arr1 [ hi ] ; } function findMissing ( arr1 , arr2 , M , N ) { if ( N == M - 1 ) document . write ( " " + findMissingUtil ( arr1 , arr2 , M ) + " " ) ; else if ( M == N - 1 ) document . write ( " " + findMissingUtil ( arr2 , arr1 , N ) + " " ) ; else document . write ( " " + " " ) ; } let arr1 = [ 1 , 4 , 5 , 7 , 9 ] ; let arr2 = [ 4 , 5 , 7 , 9 ] ; let M = arr1 . length ; let N = arr2 . length ; findMissing ( arr1 , arr2 , M , N ) ;