Ceiling in a sorted array | Function to get index of ceiling of x in arr [ low . . high ] ; If x is smaller than or equal to the first element , then return the first element ; If x is greater than the last element , then return - 1 ; get the index of middle element of arr [ low . . high ] low + ( high - low ) / 2 ; If x is same as middle element , then return mid ; If x is greater than arr [ mid ] , then either arr [ mid + 1 ] is ceiling of x or ceiling lies in arr [ mid + 1. . . high ] ; If x is smaller than arr [ mid ] , then either arr [ mid ] is ceiling of x or ceiling lies in arr [ low ... mid - 1 ] ; Driver program to check above functions
def ceilSearch ( arr , low , high , x ) : NEW_LINE INDENT if x <= arr [ low ] : NEW_LINE INDENT return low NEW_LINE DEDENT if x > arr [ high ] : NEW_LINE INDENT return - 1 NEW_LINE DEDENT mid = ( low + high ) / 2 ; NEW_LINE if arr [ mid ] == x : NEW_LINE INDENT return mid NEW_LINE DEDENT elif arr [ mid ] < x : NEW_LINE INDENT if mid + 1 <= high and x <= arr [ mid + 1 ] : NEW_LINE INDENT return mid + 1 NEW_LINE DEDENT else : NEW_LINE INDENT return ceilSearch ( arr , mid + 1 , high , x ) NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT if mid - 1 >= low and x > arr [ mid - 1 ] : NEW_LINE INDENT return mid NEW_LINE DEDENT else : NEW_LINE INDENT return ceilSearch ( arr , low , mid - 1 , x ) NEW_LINE DEDENT DEDENT DEDENT arr = [ 1 , 2 , 8 , 10 , 10 , 12 , 19 ] NEW_LINE n = len ( arr ) NEW_LINE x = 20 NEW_LINE index = ceilSearch ( arr , 0 , n - 1 , x ) ; NEW_LINE if index == - 1 : NEW_LINE INDENT print ( " Ceiling ▁ of ▁ % d ▁ doesn ' t ▁ exist ▁ in ▁ array ▁ " % x ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " ceiling ▁ of ▁ % d ▁ is ▁ % d " % ( x , arr [ index ] ) ) NEW_LINE DEDENT