Imperative:
package org.bk.karatechop class KarateChop { def chop(aNumber:Int, anArray:Array[Int]):Int = { var minIndex=0 var maxIndex = anArray.length-1 while(minIndex<=maxIndex){ var midIndex = (minIndex+maxIndex)/2 var atMidIndex = anArray(midIndex) if (aNumber>atMidIndex){ minIndex=midIndex+1 }else if(aNumber<atMidIndex){ maxIndex=midIndex-1 }else{ return midIndex } } -1 } }
Functional:
package org.bk.karatechop class KarateChopRecursive { def chop(aNumber:Int, anArray:Array[Int]):Int = { def recurse(low:Int, high:Int):Option[Int] = { (low + high)/2 match { case _ if high < low => None case mid if aNumber < anArray(mid) => recurse(low, mid - 1) case mid if aNumber > anArray(mid) => recurse(mid + 1, high) case mid => Some(mid) } } recurse(0,anArray.length-1).getOrElse(-1) } }
No comments:
Post a Comment