Create a Sorted Array Using Binary Search | Function to create a new sorted array using Binary Search ; Auxiliary Array ; if b is empty any element can be at first place ; Perform Binary Search to find the correct position of current element in the new array ; let the element should be at first index ; if a [ j ] is already present in the new array ; add a [ j ] at mid + 1. you can add it at mid ; if a [ j ] is lesser than b [ mid ] go right side ; means pos should be between start and mid - 1 ; else pos should be between mid + 1 and end ; if a [ j ] is the largest push it at last ; here max ( 0 , pos ) is used because sometimes pos can be negative as smallest duplicates can be present in the array ; Print the new generated sorted array ; Driver Code
def createSorted ( a : list , n : int ) : NEW_LINE INDENT b = [ ] NEW_LINE for j in range ( n ) : NEW_LINE INDENT if len ( b ) == 0 : NEW_LINE INDENT b . append ( a [ j ] ) NEW_LINE DEDENT else : NEW_LINE INDENT start = 0 NEW_LINE end = len ( b ) - 1 NEW_LINE pos = 0 NEW_LINE while start <= end : NEW_LINE INDENT mid = start + ( end - start ) // 2 NEW_LINE if b [ mid ] == a [ j ] : NEW_LINE INDENT b . insert ( max ( 0 , mid + 1 ) , a [ j ] ) NEW_LINE break NEW_LINE DEDENT elif b [ mid ] > a [ j ] : NEW_LINE INDENT pos = end = mid - 1 NEW_LINE DEDENT else : NEW_LINE INDENT pos = start = mid + 1 NEW_LINE DEDENT if start > end : NEW_LINE INDENT pos = start NEW_LINE b . insert ( max ( 0 , pos ) , a [ j ] ) NEW_LINE break NEW_LINE DEDENT DEDENT DEDENT DEDENT for i in range ( n ) : NEW_LINE INDENT print ( b [ i ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT a = [ 2 , 5 , 4 , 9 , 8 ] NEW_LINE n = len ( a ) NEW_LINE createSorted ( a , n ) NEW_LINE DEDENT