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)
  
  
 }
}

No comments:

Post a Comment