package Ġchapter 1 . section 4 Ċ Ċ import Ġextensions . input Prompt Ċ import Ġextensions . read All Ints Ċ import Ġextensions . readInt Ċ Ċ /** Ċ Ġ* Ġ æĹł éĩįå¤į åĢ¼ ä¹ĭ ä¸ŃçļĦ äºĮ åĪĨ æŁ¥æī¾ Ċ Ġ* ĠçĶ¨ äºĮ åĪĨ æŁ¥æī¾ å®ŀçİ° Static SE To f Ints ï¼Ī è¯· è§ģ è¡¨ 1 . 2 . 1 5 ï¼īï¼Į ä¿Ŀè¯ģ contains () çļĦ è¿Ĳè¡Į æĹ¶éĹ´ ä¸º ~ lg R ï¼Į åħ¶ä¸Ń R ä¸º åıĤæķ° æķ°ç»Ħ ä¸Ń ä¸įåĲĮ æķ´æķ° çļĦ æķ°éĩı ãĢĤ Ċ Ġ* Ċ Ġ* Ġ è§£ ï¼ļ åĪĽå»º å¯¹è±¡ æĹ¶ ï¼Į åħĪ å¯¹ æķ°ç»Ħ æİĴåºı ï¼Į åĨį åĪĽå»ºä¸Ģä¸ª åı¯ åıĺ éķ¿åº¦ çļĦ åĪĹè¡¨ ï¼Į éģįåİĨ æİĴåºı åĲİçļĦ æķ°ç»Ħ Ċ Ġ* Ġå½ĵ æķ°ç»Ħ åĢ¼ åĴĮ åĪĹè¡¨ çļĦ æľĢåĲİ ä¸Ģ ä½į ä¸įåĲĮ æĹ¶ å°Ĩ æķ°æį® æ·»åĬł åĪ° åĪĹè¡¨ ä¸Ń ï¼Į æľĢåĲİ å°Ĩ åĪĹè¡¨ è½¬ åĮĸ ä¸º æĸ° æķ°ç»Ħ Ċ Ġ* Ġåľ¨ contains æĸ¹æ³ķ ä¸Ń ä½¿çĶ¨ æĻ®éĢļ çļĦ äºĮ åĪĨ æŁ¥æī¾ åį³åı¯ Ċ Ġ* Ġ æĸ° æķ°ç»Ħ ä¸Ń ä¸į åĮħåĲ« éĩįå¤į åħĥç´ł ï¼Į æķ°ç»Ħ çļĦ éķ¿åº¦ ä¸º R ï¼Į æīĢä»¥ contains æĸ¹æ³ķ çļĦ è¿Ĳè¡Į æĹ¶éĹ´ ä¸º ~ log R Ċ Ġ*/ Ċ class ĠStatic s SE To f Ints ( array : ĠInt Array ) Ġ{ ĊĠĠĠ Ġprivate Ġval Ġordered Array : ĠInt Array ĊĊĠĠĠ Ġinit Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġsort Array Ġ= ĠInt Array ( array . size ) ĊĠĠĠĠĠĠĠ Ġarray . forEach Indexed Ġ{ Ġindex , Ġvalue Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsort Array [ index ] Ġ= Ġvalue ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġsort Array . sort () ĊĠĠĠĠĠĠĠ Ġval Ġlist Ġ= Ġmutable ListOf < Int >() ĊĠĠĠĠĠĠĠ Ġsort Array . forEach Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( list . isEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlist . add ( it ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( it Ġ!= Ġlist . last ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlist . add ( it ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġordered Array Ġ= Ġlist . to IntArray () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġcontains ( key : ĠInt ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġstart Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġvar Ġend Ġ= Ġordered Array . size Ġ- Ġ 1 ĊĠĠĠĠĠĠĠ Ġwhile Ġ( start Ġ<= Ġend ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġmid Ġ= Ġ( start Ġ+ Ġend ) Ġ/ Ġ 2 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhen Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġordered Array [ mid ] Ġ== Ġkey Ġ-> Ġreturn Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġordered Array [ mid ] Ġ< Ġkey Ġ-> Ġstart Ġ= Ġmid Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġordered Array [ mid ] Ġ> Ġkey Ġ-> Ġend Ġ= Ġmid Ġ- Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġfalse ĊĠĠĠ Ġ} Ċ } Ċ Ċ fun Ġmain () Ġ{ ĊĠĠĠ Ġinput Prompt () ĊĠĠĠ Ġval Ġkey Ġ= Ġread Int () ĊĠĠĠ Ġval Ġarray Ġ= Ġread All Ints () ĊĠĠĠ Ġval Ġset Ġ= ĠStatic s SE To f Ints ( array ) ĊĠĠĠ Ġprintln ( array . join ToString ()) ĊĠĠĠ Ġprintln (" Array Ġ${ if Ġ( set . contains ( key )) Ġ" contains " Ġelse Ġ" dose Ġnot Ġcontain "} Ġ$ key ") Ċ }