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.
'   If not found returns -1
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  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

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

StackExchange Code Review Q#74702, answer score: 5