Sunday, September 12, 2010

Karate Chop - An Imperative and Functional implementation

Karate Chop is a Kata about implementing binary search five different ways. I could come up with 2 obvious ways - an imperative style with iteration and a functional style based on the solution inspired by this site . So here goes:

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)

}
}
```