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
< ? php function findMissingUtil ( $ arr1 , $ arr2 , $ N ) { if ( $ N == 1 ) return $ arr1 [ 0 ] ; if ( $ arr1 [ 0 ] != $ arr2 [ 0 ] ) return $ arr1 [ 0 ] ; $ lo = 0 ; $ hi = $ N - 1 ; while ( $ lo < $ hi ) { $ mid = ( $ lo + $ hi ) / 2 ; 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 ) echo " Missing ▁ Element ▁ is ▁ " , findMissingUtil ( $ arr1 , $ arr2 , $ M ) ; else if ( $ M == $ N - 1 ) echo " Missing ▁ Element ▁ is ▁ " , findMissingUtil ( $ arr2 , $ arr1 , $ N ) ; else echo " Invalid ▁ Input " ; } $ arr1 = array ( 1 , 4 , 5 , 7 , 9 ) ; $ arr2 = array ( 4 , 5 , 7 , 9 ) ; $ M = count ( $ arr1 ) ; $ N = count ( $ arr2 ) ; findMissing ( $ arr1 , $ arr2 , $ M , $ N ) ; ? >