# Karate Chop Kata

I had some time to kill today, and I found the Karate Chop Kata.

Specification:

Write a binary chop method that takes an integer search target and a sorted array of integers. It should return the integer index of the target in the array, or -1 if the target is not in the array.

I've never implemented a binary search before. So, even though all of my tests pass, I'm not sure that I've covered all of the corner cases. It also doesn't look very elegant. How can I improve on this?

I'm also still not sure that I'm unit testing in a "proper" way. How can I improve them? (Please keep in mind that Rubberduck automatically inserts boilerplate for new test methods.)

## Chop

Option Explicit

' Returns index of the target number in a given array.
Public Function Chop(target As Long, Arr() As Long, Optional midpoint As Long = -1) As Long
Dim result As Long
Dim currentTest As Long

If Not IsArrayAllocated(Arr) Then
Chop = -1
Exit Function
End If

If midpoint < 0 Then
midpoint = UBound(Arr) \ 2  'integer division
End If

currentTest = Arr(midpoint)

If target = currentTest Then
result = midpoint
ElseIf midpoint = 0 Or (Arr(UBound(Arr)) < target) Then
Else
If target > currentTest Then
midpoint = midpoint + (midpoint \ 2) ' go up by half
If midpoint > UBound(Arr) Then midpoint = UBound(Arr)
Else
midpoint = midpoint \ 2
End If

result = Chop(target, Arr, midpoint)
End If

Chop = result
End Function

'Borrorwed from Chip Pearson
' http://www.cpearson.com/excel/isarrayallocated.aspx
Function IsArrayAllocated(Arr As Variant) As Boolean
On Error Resume Next
IsArrayAllocated = IsArray(Arr) And _
Not IsError(LBound(Arr, 1)) And _
LBound(Arr, 1) <= UBound(Arr, 1)
End Function


## Rubberduck Unit Tests

Option Explicit

Option Private Module

'@TestModule
Private Assert As New Rubberduck.AssertClass

'@TestMethod
Public Sub EmptyArrayReturnsNegativeOne()
On Error GoTo TestFail

Arrange:
Const expected As Long = -1
Dim integers() As Long
Act:

Assert:
Assert.AreEqual expected, Chop(2, integers)

TestExit:
Exit Sub
TestFail:
If Err.Number <> 0 Then
Assert.Fail "Test raised an error: #" & Err.Number & " - " & Err.Description
Else
Resume TestExit
End If
End Sub

'@TestMethod
Public Sub TargetNotInArrayReturnsNegativeOne()
On Error GoTo TestFail
Arrange:
Const expected As Long = -1
Const target As Long = 2
Dim integers(0) As Long
integers(0) = 3
Act:

Assert:
Assert.AreEqual expected, Chop(target, integers)

TestExit:
Exit Sub
TestFail:
If Err.Number <> 0 Then
Assert.Fail "Test raised an error: #" & Err.Number & " - " & Err.Description
Else
Resume TestExit
End If
End Sub

'@TestMethod
Public Sub TargetNotInArrayReturnsNegativeOne_LargerArray()
On Error GoTo TestFail
Arrange:
Const expected As Long = -1
Act:

Assert:
Assert.AreEqual expected, Chop(10, EvenSizeArray)

TestExit:
Exit Sub
TestFail:
If Err.Number <> 0 Then
Assert.Fail "Test raised an error: #" & Err.Number & " - " & Err.Description
Else
Resume TestExit
End If
End Sub

'@TestMethod
Public Sub OddSizeArray_FirstReturnsZero()
On Error GoTo TestFail
Arrange:
Const expected As Long = 0
Act:

Assert:
Assert.AreEqual expected, Chop(1, OddSizeArray)

TestExit:
Exit Sub
TestFail:
If Err.Number <> 0 Then
Assert.Fail "Test raised an error: #" & Err.Number & " - " & Err.Description
Else
Resume TestExit
End If
End Sub

'@TestMethod
Public Sub OddSizeArray_MiddleReturnsTwo()
On Error GoTo TestFail
Arrange:
Const expected As Long = 2
Act:

Assert:
Assert.AreEqual expected, Chop(3, OddSizeArray)

TestExit:
Exit Sub
TestFail:
If Err.Number <> 0 Then
Assert.Fail "Test raised an error: #" & Err.Number & " - " & Err.Description
Else
Resume TestExit
End If
End Sub

'@TestMethod
Public Sub OddSizeArray_LastReturnsFour()
On Error GoTo TestFail
Arrange:
Const expected As Long = 4
Act:

Assert:
Assert.AreEqual expected, Chop(5, OddSizeArray)

TestExit:
Exit Sub
TestFail:
If Err.Number <> 0 Then
Assert.Fail "Test raised an error: #" & Err.Number & " - " & Err.Description
Else
Resume TestExit
End If
End Sub

'@TestMethod
Public Sub EvenSizeArray_FirstReturnsZero()
On Error GoTo TestFail

Arrange:
Const expected As Long = 0
Act:

Assert:
Assert.AreEqual expected, Chop(1, EvenSizeArray)

TestExit:
Exit Sub
TestFail:
If Err.Number <> 0 Then
Assert.Fail "Test raised an error: #" & Err.Number & " - " & Err.Description
Else
Resume TestExit
End If
End Sub

'@TestMethod
Public Sub EvenSizeArray_LastReturnsFive()
On Error GoTo TestFail

Arrange:
Const expected As Long = 5
Act:

Assert:
Assert.AreEqual expected, Chop(6, EvenSizeArray)

TestExit:
Exit Sub
TestFail:
If Err.Number <> 0 Then
Assert.Fail "Test raised an error: #" & Err.Number & " - " & Err.Description
Else
Resume TestExit
End If
End Sub

'@TestMethod
Public Sub EvenSizeArray_NextToLastReturnsFour()
On Error GoTo TestFail

Arrange:
Const expected As Long = 4
Act:

Assert:
Assert.AreEqual expected, Chop(5, EvenSizeArray)

TestExit:
Exit Sub
TestFail:
If Err.Number <> 0 Then
Assert.Fail "Test raised an error: #" & Err.Number & " - " & Err.Description
Else
Resume TestExit
End If
End Sub

Private Function OddSizeArray() As Long()
Dim result(0 To 4) As Long
Dim i As Long
For i = LBound(result) To UBound(result)
result(i) = i + 1
Next
OddSizeArray = result
End Function

Private Function EvenSizeArray() As Long()
Dim result(0 To 5) As Long
Dim i As Long
For i = LBound(result) To UBound(result)
result(i) = i + 1
Next
EvenSizeArray = result
End Function


I see some weird stuff going on here, let me see if I can verbalize my concerns

If target = currentTest Then
result = midpoint
ElseIf midpoint = 0 Or (Arr(UBound(Arr)) < target) Then
Else
If target > currentTest Then
midpoint = midpoint + (midpoint \ 2) ' go up by half
If midpoint > UBound(Arr) Then midpoint = UBound(Arr)
Else
midpoint = midpoint \ 2
End If

result = Chop(target, Arr, midpoint)
End If


One of the first things I would do is to move the ElseIf statement out front, dump out right away, but I have a feeling that this won't happen as often as the current If statement and that the Arr(UBound(Arr)) < target must be more Resource intensive than comparing two objects.

so I guess that I am going to leave that one alone.

The next thing that I noticed was that you nested an If structure inside the Else statement, and it made me stop and think for a little bit.

So I wrote it out like this

If target = currentTest Then
result = midpoint
ElseIf midpoint = 0 Or (Arr(UBound(Arr)) < target) Then
Else If target > currentTest Then
midpoint = midpoint + (midpoint \ 2) ' go up by half
If midpoint > UBound(Arr) Then midpoint = UBound(Arr)
result = Chop(target, Arr, midpoint)
Else
midpoint = midpoint \ 2
result = Chop(target, Arr, midpoint)
End If


But then the code isn't dry, it repeats result = Chop(target, Arr, midpoint) which is annoying, and now I understand why you did it like that, it smells but seems to be what is necessary.

But your If statement structure is inconsistent, you one line in a weird spot and I almost missed it. You were also missing an End If statement. I came up with

If target = currentTest Then
result = midpoint
ElseIf midpoint = 0 Or (Arr(UBound(Arr)) < target) Then
Else
If target > currentTest Then
midpoint = midpoint + (midpoint \ 2) ' go up by half
If midpoint > UBound(Arr) Then
midpoint = UBound(Arr)
End If
Else
midpoint = midpoint \ 2
End If
result = Chop(target, Arr, midpoint)
End If

• I don't think I can move the ElseIf out front because I think I need to check to see if a match was found before I say it wasn't found, but otherwise spot on. (Particularly that one line If...What was I thinking?) Dec 31, 2014 at 21:06
• I figured that there had to be a reason that you had that second and not first.
– Malachi
Dec 31, 2014 at 21:17
1. Even though it matches the spec, Chop isn't a very good name for what this function does. IndexOf would be a better name.
2. Ubound(Arr) gets called in this code a lot. It happens more than enough to declare a variable for it.
3. All of the parameters are being implicitly passed ByRef which isn't nice. (And you have no excuse. The add-in you're using warns you about this.)
4. The optional parameter for midpoint is okay, but it exposes implementation details to the client. It would be better to create a private function that does all of the heavy lifting. It can require that the midpoint be specified.

Public Function IndexOf(ByVal target As Long, ByRef Arr() As Long) As Long
IndexOf = RecursiveIndexOf(target, Arr, -1)
End Function

5. This is a useless comment. If the maintainer doesn't know the difference between / and \ they can look it up.

midpoint = upperBoundry \ 2  'integer division

6. -1 is a magic number with two separate meanings. Constants should be defined.

Private Const DefaultMidpoint As Integer = -1
Public Const IndexOfResultNotFound As Long = -1

7. It's not semantically correct to initialize the midpoint if midpoint < 0. It's correct to initialize it if midpoint = DefaultMidpoint.

If midpoint = DefaultMidpoint Then
midpoint = upperBoundry \ 2
End If

8. It's not quite as DRY, but an ElseIf here instead of an Or improves readability. Considering it's merely assignment, I think it's a good change.

ElseIf midpoint = 0 Or (Arr(upperBoundry) < target) Then
result = IndexOfResultNotFound
Else


Becomes

ElseIf midpoint = 0 Then
result = IndexOfResultNotFound

ElseIf Arr(upperBoundry) < target Then
result = IndexOfResultNotFound

Else

9. This logic can and should be extracted into a GetNextMidpoint function.

    Else
If target > currentTest Then
midpoint = midpoint + (midpoint \ 2) ' go up by half
If midpoint > upperBoundry Then
midpoint = upperBoundry
End If
Else
midpoint = midpoint \ 2
End If

result = RecursiveIndexOf(target, Arr, midpoint)
End If


Which gives us the refactored code below.

Option Explicit

Private Const DefaultMidpoint As Integer = -1
Public Const IndexOfResultNotFound As Long = -1

' Returns index of the target number in a given array.
Public Function IndexOf(ByVal target As Long, ByRef Arr() As Long) As Long
IndexOf = RecursiveIndexOf(target, Arr, DefaultMidpoint)
End Function

Private Function RecursiveIndexOf(ByVal target As Long, ByRef Arr() As Long, ByVal midpoint As Long)
Dim result As Long
Dim currentTest As Long

If Not IsArrayAllocated(Arr) Then
RecursiveIndexOf = IndexOfResultNotFound
Exit Function
End If

Dim upperBoundry As Long
upperBoundry = UBound(Arr)

If midpoint = DefaultMidpoint Then
midpoint = upperBoundry \ 2
End If

currentTest = Arr(midpoint)

If target = currentTest Then
result = midpoint

ElseIf midpoint = 0 Then
result = IndexOfResultNotFound

ElseIf Arr(upperBoundry) < target Then
result = IndexOfResultNotFound

Else
midpoint = GetNextMidpoint(currentTest, target, upperBoundry, midpoint)
result = RecursiveIndexOf(target, Arr, midpoint)
End If

RecursiveIndexOf = result
End Function

Private Function GetNextMidpoint(ByVal current As Long, ByVal target As Long, ByVal upperBoundry As Long, ByVal midpoint As Long) As Long
Dim result As Long

If target > current Then
result = midpoint + (midpoint \ 2) ' go up by half
If result > upperBoundry Then
result = upperBoundry
End If
Else
result = midpoint \ 2
End If

GetNextMidpoint = result

End Function

'Borrorwed from Chip Pearson
' http://www.cpearson.com/excel/isarrayallocated.aspx
Function IsArrayAllocated(Arr As Variant) As Boolean
On Error Resume Next
IsArrayAllocated = IsArray(Arr) And _
Not IsError(LBound(Arr, 1)) And _
LBound(Arr, 1) <= UBound(Arr, 1)
End Function


I'll just comment on your unit testing code.

Your unit tests aren't really AAA:

Arrange:
Const expected As Long = -1
Dim integers() As Long
Act:

Assert:
Assert.AreEqual expected, Chop(2, integers)


You're doing the "Act" step in the "Assert" part, which should do nothing other than assert - like this:

Arrange:
Const expected As Long = -1
Dim integers() As Long
Dim result As Long

Act:
result = Chop(2, integers)

Assert:
Assert.AreEqual expected, result


OddSizeArray and EvenSizeArray are setup code that shouldn't be called in the "Act" part (even less so in the "Assert" part).

Rubberduck unit tests allow you to move the call to that setup code outside the actual test method, so that creating the setup array doesn't affect the measurements (although 0-1ms is arguably not a big deal).

Private oddSizedArray() As Long
Private evenSizedArray() As Long


And then add a TestInitialize method that will populate them:

'@TestInitialize
Public Sub SetupTestArrays()
oddSizedArray = OddSizeArray
evenSizedArray = EvenSizeArray
End Sub


Alternatively you can drop the '@TestInitialize marker comment and name the method like this:

Public Sub TestInitialize()


Every method called TestInitialize or marked with a @TestInitialize marker right above the signature line will execute before every unit test in a test module, i.e. before Rubberduck makes the timed method call to run the test method. As a result, setting up the two arrays will not count in the Duration of a test.

The fields should "die" by themselves when all tests have executed, but if you want you can also add a TestCleanup method that runs after every unit test, to deallocate the arrays:

 Public Sub TestCleanup()
Erase oddSizedArray
Erase evenSizedArray
End Sub


In this specific case, we're talking about nanoseconds. But in other unit testing code you could be setting up a mock of an interface implementation to supply fake content to a method that would otherwise access a database or the file system: that setup code belongs in the "Arrange" part of your tests - not in "Act", not in "Assert".

• For the record, Rubberduck didn't support this when I first wrote these tests. =;)- May 17, 2015 at 19:12