package Ġeasy Ċ Ċ class ĠSearch Insert Position Solution Ġ{ ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠTime ĠComplex ity : ĠO ( log ( n )) ĊĠĠĠĠ Ġ* ĠSpace ĠComplex ity : ĠO ( 1 ) ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġsearch Insert Using Binary Search ( nums : ĠInt Array , Ġtarget : ĠInt ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġlow Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġvar Ġhigh Ġ= Ġnums . size ĊĠĠĠĠĠĠĠ Ġwhile Ġ( low Ġ<= Ġhigh ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġmid Ġ= Ġ( low Ġ+ Ġhigh ) Ġ/ Ġ 2 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhen Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnums [ mid ] Ġ< Ġtarget Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlow Ġ= Ġmid Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnums [ mid ] Ġ> Ġtarget Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġhigh Ġ= Ġmid Ġ- Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġmid ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġlow ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠTime ĠComplex ity : ĠO ( n ) ĊĠĠĠĠ Ġ* ĠSpace ĠComplex ity : ĠO ( 1 ) ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġsearch Insert Using Linear Scan ( nums : ĠInt Array , Ġtarget : ĠInt ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġnums . indices ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( nums [ i ] Ġ>= Ġtarget ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġi ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġnums . size ĊĠĠĠ Ġ} Ċ } Ċ