Find missing element in a sorted array of consecutive numbers | Function to return the missing element ; Check if middle element is consistent ; No inconsistency till middle elements When missing element is just after the middle element ; Move right ; Inconsistency found When missing element is just before the middle element ; Move left ; No missing element found ; Driver code
< ? php function findMissing ( $ arr , $ n ) { $ l = 0 ; $ h = $ n - 1 ; while ( $ h > $ l ) { $ mid = floor ( $ l + ( $ h - $ l ) / 2 ) ; if ( $ arr [ $ mid ] - $ mid == $ arr [ 0 ] ) { if ( $ arr [ $ mid + 1 ] - $ arr [ $ mid ] > 1 ) return $ arr [ $ mid ] + 1 ; else { $ l = $ mid + 1 ; } } else { if ( $ arr [ $ mid ] - $ arr [ $ mid - 1 ] > 1 ) return $ arr [ $ mid ] - 1 ; else { $ h = $ mid - 1 ; } } } return -1 ; } $ arr = array ( -9 , -8 , -7 , -5 , - 4 , -3 , -2 , -1 , 0 ) ; $ n = count ( $ arr ) ; echo findMissing ( $ arr , $ n ) ; ? >