package Ġle et code Ċ Ċ /** Ċ Ġ* Ġ# Ġ 1 5 3 . ĠFind ĠMinimum Ġin ĠRot ated ĠSorted ĠArray Ċ Ġ* Ċ Ġ* ĠSup pose Ġan Ġarray Ġof Ġlength Ġn Ġsorted Ġin Ġascending Ġorder Ġis Ġrotated Ġbetween Ġ 1 Ġand Ġn Ġtimes . ĠFor Ġexample , Ċ Ġ* Ġthe Ġarray Ġ` nums Ġ= Ġ[ 0 , 1 , 2 , 4 , 5 , 6 , 7 ]` Ġmight Ġbecome : Ċ Ġ* Ċ Ġ* Ġ* Ġ`[ 4 , 5 , 6 , 7 , 0 , 1 , 2 ]` Ġif Ġit Ġwas Ġrotated Ġ 4 Ġtimes . Ċ Ġ* Ġ* Ġ`[ 0 , 1 , 2 , 4 , 5 , 6 , 7 ]` Ġif Ġit Ġwas Ġrotated Ġ 7 Ġtimes . Ċ Ġ* ĠNotice Ġthat Ġrot ating Ġan Ġarray Ġ`[ a [ 0 ], Ġa [ 1 ], Ġa [ 2 ], Ġ..., Ġa [ n - 1 ]] ` Ġ 1 Ġtime Ġresults Ġin Ġthe Ġarray Ċ Ġ* Ġ`[ a [ n - 1 ], Ġa [ 0 ], Ġa [ 1 ], Ġa [ 2 ], Ġ..., Ġa [ n - 2 ]] `. Ċ Ġ* Ċ Ġ* ĠGiven Ġthe Ġsorted Ġrotated Ġarray Ġnums Ġof Ġunique Ġelements , Ġreturn Ġthe Ġminimum Ġelement Ġof Ġthis Ġarray . Ċ Ġ* Ċ Ġ* ĠYou Ġmust Ġwrite Ġan Ġalgorithm Ġthat Ġruns Ġin ĠO ( log Ġn ) Ġtime . Ċ Ġ* Ċ Ġ* Ġ## ĠExample Ġ 1 : Ċ Ġ* Ġ``` Ċ Ġ* ĠInput : Ġnums Ġ= Ġ[ 3 , 4 , 5 , 1 , 2 ] Ċ Ġ* ĠOutput : Ġ 1 Ċ Ġ* ĠEx planation : ĠThe Ġoriginal Ġarray Ġwas Ġ[ 1 , 2 , 3 , 4 , 5 ] Ġrotated Ġ 3 Ġtimes . Ċ Ġ* Ġ``` Ċ Ġ* Ċ Ġ* Ġ## ĠExample Ġ 2 : Ċ Ġ* Ġ``` Ċ Ġ* ĠInput : Ġnums Ġ= Ġ[ 4 , 5 , 6 , 7 , 0 , 1 , 2 ] Ċ Ġ* ĠOutput : Ġ 0 Ċ Ġ* ĠEx planation : ĠThe Ġoriginal Ġarray Ġwas Ġ[ 0 , 1 , 2 , 4 , 5 , 6 , 7 ] Ġand Ġit Ġwas Ġrotated Ġ 4 Ġtimes . Ċ Ġ* Ġ``` Ċ Ġ* Ċ Ġ* Ġ## ĠExample Ġ 3 : Ċ Ġ* Ġ``` Ċ Ġ* ĠInput : Ġnums Ġ= Ġ[ 1 1 , 1 3 , 1 5 , 1 7 ] Ċ Ġ* ĠOutput : Ġ 1 1 Ċ Ġ* ĠEx planation : ĠThe Ġoriginal Ġarray Ġwas Ġ[ 1 1 , 1 3 , 1 5 , 1 7 ] Ġand Ġit Ġwas Ġrotated Ġ 4 Ġtimes . Ċ Ġ* Ġ``` Ċ Ġ* Ċ Ġ* Ġ## ĠConstraints : Ċ Ġ* Ċ Ġ* Ġ* Ġn Ġ== Ġnums . length Ċ Ġ* Ġ* Ġ 1 Ġ<= Ġn Ġ<= Ġ 5 0 0 0 Ċ Ġ* Ġ* Ġ- 5 0 0 0 Ġ<= Ġnums [ i ] Ġ<= Ġ 5 0 0 0 Ċ Ġ* Ġ* ĠAll Ġthe Ġintegers Ġof Ġnums Ġare Ġunique . Ċ Ġ* Ġ* Ġnums Ġis Ġsorted Ġand Ġrotated Ġbetween Ġ 1 Ġand Ġn Ġtimes . Ċ Ġ* Ġ``` Ċ Ġ*/ Ċ @ Suppress (" ClassName ") Ċ class Ġ` 1 5 3 _ Find _ Minimum _ In _ Rot ated _ Sorted _ Array ` Ġ{ ĊĠ Ġclass ĠSolution Ġ{ ĊĠĠĠ Ġfun Ġfind Min ( nums : ĠInt Array ): ĠInt Ġ{ ĊĠĠĠĠĠ Ġvar Ġlow Ġ= Ġ 0 ĊĠĠĠĠĠ Ġvar Ġhigh Ġ= Ġnums . size Ġ- Ġ 1 ĊĊĠĠĠĠĠ Ġwhile Ġ( low Ġ< Ġhigh ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġmid Ġ= Ġlow Ġ+ Ġ( high Ġ- Ġlow ) Ġ/ Ġ 2 ĊĠĠĠĠĠĠĠ Ġif Ġ( nums [ mid ] Ġ< Ġnums [ high ]) Ġ{ ĊĠĠĠĠĠĠĠĠĠ Ġhigh Ġ= Ġmid ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠ Ġlow Ġ= Ġmid Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠ Ġreturn Ġnums [ low ] ĊĠĠĠ Ġ} ĊĠ Ġ} Ċ }