Search an element in a sorted and rotated array with duplicates | Function to return the index of the key in arr [ l . . h ] if the key is present otherwise return - 1 ; The tricky case , just update left and right ; If arr [ l ... mid ] is sorted ; As this subarray is sorted , we can quickly check if key lies in any of the halves ; If key does not lie in the first half subarray then divide the other half into two subarrays such that we can quickly check if key lies in the other half ; If arr [ l . . mid ] first subarray is not sorted then arr [ mid ... h ] must be sorted subarray ; Driver code
def search ( arr , l , h , key ) : NEW_LINE INDENT if ( l > h ) : NEW_LINE INDENT return - 1 ; NEW_LINE DEDENT mid = ( l + h ) // 2 ; NEW_LINE if ( arr [ mid ] == key ) : NEW_LINE INDENT return mid ; NEW_LINE DEDENT if ( ( arr [ l ] == arr [ mid ] ) and ( arr [ h ] == arr [ mid ] ) ) : NEW_LINE INDENT l += 1 ; NEW_LINE h -= 1 ; NEW_LINE return search ( arr , l , h , key ) NEW_LINE DEDENT if ( arr [ l ] <= arr [ mid ] ) : NEW_LINE INDENT if ( key >= arr [ l ] and key <= arr [ mid ] ) : NEW_LINE INDENT return search ( arr , l , mid - 1 , key ) ; NEW_LINE DEDENT return search ( arr , mid + 1 , h , key ) ; NEW_LINE DEDENT if ( key >= arr [ mid ] and key <= arr [ h ] ) : NEW_LINE INDENT return search ( arr , mid + 1 , h , key ) ; NEW_LINE DEDENT return search ( arr , l , mid - 1 , key ) ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 3 , 3 , 1 , 2 , 3 , 3 ] ; NEW_LINE n = len ( arr ) ; NEW_LINE key = 3 ; NEW_LINE print ( search ( arr , 0 , n - 1 , key ) ) ; NEW_LINE DEDENT