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
function createSorted ( a , n ) { var b = [ ] ; for ( var j = 0 ; j < n ; j ++ ) { if ( b . length == 0 ) b . push ( a [ j ] ) ; else { var start = 0 , end = b . length - 1 ; var pos = 0 ; while ( start <= end ) { var mid = start + parseInt ( ( end - start ) / 2 ) ; if ( b [ mid ] === a [ j ] ) { b . insert ( Math . max ( 0 , mid + 1 ) , a [ j ] ) ; break ; } else if ( b [ mid ] > a [ j ] ) pos = end = mid - 1 ; else pos = start = mid + 1 ; if ( start > end ) { pos = start ; b . insert ( Math . max ( 0 , pos ) , a [ j ] ) ; break ; } } } } for ( var i = 0 ; i < n ; i ++ ) document . write ( b [ i ] + " " ) ; } Array . prototype . insert = function ( index , item ) { this . splice ( index , 0 , item ) ; } ; var a = [ 2 , 5 , 4 , 9 , 8 ] ; var n = a . length ; createSorted ( a , n ) ;