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