Create a Sorted Array Using Binary Search | Java program to 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
import java . util . * ; class GFG { static void createSorted ( int a [ ] , int n ) { Vector < Integer > b = new Vector < > ( ) ; for ( int j = 0 ; j < n ; j ++ ) { if ( b . isEmpty ( ) ) b . add ( a [ j ] ) ; else { int start = 0 , end = b . size ( ) - 1 ; int pos = 0 ; while ( start <= end ) { int mid = start + ( end - start ) / 2 ; if ( b . get ( mid ) == a [ j ] ) { b . add ( ( Math . max ( 0 , mid + 1 ) ) , a [ j ] ) ; break ; } else if ( b . get ( mid ) > a [ j ] ) pos = end = mid - 1 ; else pos = start = mid + 1 ; if ( start > end ) { pos = start ; b . add ( Math . max ( 0 , pos ) , a [ j ] ) ; break ; } } } } for ( int i = 0 ; i < n ; i ++ ) System . out . print ( b . get ( i ) + " ▁ " ) ; } public static void main ( String args [ ] ) { int a [ ] = { 2 , 5 , 4 , 9 , 8 } ; int n = a . length ; createSorted ( a , n ) ; } }