Search in an almost sorted array | A recursive binary search based function . It returns index of x in given array arr [ l . . r ] is present , otherwise - 1 ; If the element is present at one of the middle 3 positions ; If element is smaller than mid , then it can only be present in left subarray ; Else the element can only be present in right subarray ; We reach here when element is not present in array ; Driver Code
def binarySearch ( arr , l , r , x ) : NEW_LINE INDENT if ( r >= l ) : NEW_LINE INDENT mid = int ( l + ( r - l ) / 2 ) NEW_LINE if ( arr [ mid ] == x ) : return mid NEW_LINE if ( mid > l and arr [ mid - 1 ] == x ) : NEW_LINE INDENT return ( mid - 1 ) NEW_LINE DEDENT if ( mid < r and arr [ mid + 1 ] == x ) : NEW_LINE INDENT return ( mid + 1 ) NEW_LINE DEDENT if ( arr [ mid ] > x ) : NEW_LINE INDENT return binarySearch ( arr , l , mid - 2 , x ) NEW_LINE DEDENT return binarySearch ( arr , mid + 2 , r , x ) NEW_LINE DEDENT return - 1 NEW_LINE DEDENT arr = [ 3 , 2 , 10 , 4 , 40 ] NEW_LINE n = len ( arr ) NEW_LINE x = 4 NEW_LINE result = binarySearch ( arr , 0 , n - 1 , x ) NEW_LINE if ( result == - 1 ) : NEW_LINE INDENT print ( " Element ▁ is ▁ not ▁ present ▁ in ▁ array " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " Element ▁ is ▁ present ▁ at ▁ index " , result ) NEW_LINE DEDENT