Find index of an extra element present in one sorted array | Returns index of extra element in arr1 [ ] . n is size of arr2 [ ] . Size of arr1 [ ] is n - 1. ; left and right are end points denoting the current range . ; If middle element is same of both arrays , it means that extra element is after mid so we update left to mid + 1 ; If middle element is different of the arrays , it means that the index we are searching for is either mid , or before mid . Hence we update right to mid - 1. ; when right is greater than left our search is complete . ; Driver code ; Solve is passed both arrays
def findExtra ( arr1 , arr2 , n ) : NEW_LINE INDENT left = 0 NEW_LINE right = n - 1 NEW_LINE while ( left <= right ) : NEW_LINE INDENT mid = ( int ) ( ( left + right ) / 2 ) NEW_LINE if ( arr2 [ mid ] == arr1 [ mid ] ) : NEW_LINE INDENT left = mid + 1 NEW_LINE DEDENT else : NEW_LINE INDENT index = mid NEW_LINE right = mid - 1 NEW_LINE DEDENT DEDENT return index NEW_LINE DEDENT arr1 = [ 2 , 4 , 6 , 8 , 10 , 12 , 13 ] NEW_LINE arr2 = [ 2 , 4 , 6 , 8 , 10 , 12 ] NEW_LINE n = len ( arr2 ) NEW_LINE print ( findExtra ( arr1 , arr2 , n ) ) NEW_LINE