// There Ġis Ġan Ġinteger Ġarray Ġnums Ġsorted Ġin Ġascending Ġorder Ġ( with Ġdistinct Ċ // values ). Ġ Ċ // Ċ // ĠPri or Ġto Ġbeing Ġpassed Ġto Ġyour Ġfunction , Ġnums Ġis Ġpossibly Ġrotated Ġat Ġan Ġ Ċ // unknown Ġpivot Ġindex Ġk Ġ( 1 Ġ<= Ġk Ġ< Ġnums . length ) Ġsuch Ġthat Ġthe Ġresulting Ġarray Ġis Ġ[ nums [ k ] Ċ // , Ġnums [ k + 1 ], Ġ..., Ġnums [ n - 1 ], Ġnums [ 0 ], Ġnums [ 1 ], Ġ..., Ġnums [ k - 1 ]] Ġ( 0 - indexed ). ĠFor Ġ Ċ // example , Ġ[ 0 , 1 , 2 , 4 , 5 , 6 , 7 ] Ġmight Ġbe Ġrotated Ġat Ġpivot Ġindex Ġ 3 Ġand Ġbecome Ġ[ 4 , 5 , 6 , 7 , 0 Ċ // , 1 , 2 ]. Ġ Ċ // Ċ // ĠGiven Ġthe Ġarray Ġnums Ġafter Ġthe Ġpossible Ġrotation Ġand Ġan Ġinteger Ġtarget , Ġ Ċ // return Ġthe Ġindex Ġof Ġtarget Ġif Ġit Ġis Ġin Ġnums , Ġor Ġ- 1 Ġif Ġit Ġis Ġnot Ġin Ġnums . Ġ Ċ // Ċ // ĠYou Ġmust Ġwrite Ġan Ġalgorithm Ġwith ĠO ( log Ġn ) Ġruntime Ġcomplexity . Ġ Ċ // Ċ // Ġ Ċ // ĠExample Ġ 1 : Ġ Ċ // ĠInput : Ġnums Ġ= Ġ[ 4 , 5 , 6 , 7 , 0 , 1 , 2 ], Ġtarget Ġ= Ġ 0 Ċ // Output : Ġ 4 Ċ // ĠExample Ġ 2 : Ġ Ċ // ĠInput : Ġnums Ġ= Ġ[ 4 , 5 , 6 , 7 , 0 , 1 , 2 ], Ġtarget Ġ= Ġ 3 Ċ // Output : Ġ- 1 Ċ // ĠExample Ġ 3 : Ġ Ċ // ĠInput : Ġnums Ġ= Ġ[ 1 ], Ġtarget Ġ= Ġ 0 Ċ // Output : Ġ- 1 Ċ // Ġ Ċ // Ġ Ċ // ĠConstraints : Ġ Ċ // Ċ // Ġ Ċ // Ġ 1 Ġ<= Ġnums . length Ġ<= Ġ 5 0 0 0 Ġ Ċ // Ġ- 1 0 âģ ´ Ġ<= Ġnums [ i ] Ġ<= Ġ 1 0 âģ ´ Ġ Ċ // ĠAll Ġvalues Ġof Ġnums Ġare Ġunique . Ġ Ċ // Ġnums Ġis Ġan Ġascending Ġarray Ġthat Ġis Ġpossibly Ġrotated . Ġ Ċ // Ġ- 1 0 âģ ´ Ġ<= Ġtarget Ġ<= Ġ 1 0 âģ ´ Ġ Ċ // Ġ Ċ // ĠRelated ĠTop ics ĠArray ĠBinary ĠSearch ĠðŁĳį Ġ 1 0 5 4 0 ĠðŁĳ İ Ġ 7 7 2 ĊĊ Ċ package Ġle et code Problem . leetcode . editor . en Ċ Ċ class ĠSearch In Rot ated Sorted Array Ġ{ ĊĠĠĠ Ġfun Ġsolution () Ġ{ ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// below Ġcode Ġwill Ġbe Ġused Ġfor Ġsubmission Ġto Ġle et code Ġ( using Ġplugin Ġof Ġcourse ) ĊĠĠĠ Ġ// leetcode Ġsubmit Ġregion Ġbegin ( Pro hibit Ġmodification Ġand Ġdeletion ) ĊĠĠĠ Ġclass ĠSolution Ġ{ ĊĠĠĠĠĠĠĠ Ġfun Ġsearch ( nums : ĠInt Array , Ġtarget : ĠInt ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġl Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġr Ġ= Ġnums . size Ġ- Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġt Ġ= 4 ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( l Ġ<= Ġr ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġm Ġ= Ġl Ġ+ Ġ( r Ġ- Ġl ) Ġ/ Ġ 2 Ġ// ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( nums [ m ] Ġ== Ġtarget ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġm ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( nums [ l ] Ġ<= Ġnums [ m ]) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( target Ġ> Ġnums [ m ] Ġ|| Ġtarget Ġ< Ġnums [ l ]) Ġl Ġ= Ġm Ġ+ Ġ 1 Ġelse Ġr Ġ= Ġm Ġ- Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( target Ġ< Ġnums [ m ] Ġ|| Ġtarget Ġ> Ġnums [ r ]) Ġr Ġ= Ġm Ġ- Ġ 1 Ġelse Ġl Ġ= Ġm Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġ- 1 ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ // leetcode Ġsubmit Ġregion Ġend ( Pro hibit Ġmodification Ġand Ġdeletion ) Ċ Ċ } Ċ Ċ fun Ġmain () Ġ{ ĊĠĠĠ ĠSearch In Rot ated Sorted Array . Solution (). search ( int ArrayOf ( 4 , 5 , 6 , 7 , 0 , 1 , 2 ) Ġ, Ġ 4 ) Ċ } ĊĠĠ ĊĊ