Binary Search of sorted array in Nemerle

binarySearchDemo.n

#pragma indent

using System.Console

module Program
  public Main() : void
    def items = array[1,2,2,2,2,2,2,2,4,8,10,12]
    def assertIndexOfXisY(item : int, expected : int)
       def actual = Demo.BinarySearch(items, item)
       WriteLine((if(actual == expected) "Correct  " else "Incorrect") + " for item: " + item)
    assertIndexOfXisY(1, 0)
    assertIndexOfXisY(8, 9)
    assertIndexOfXisY(0, -1)
    assertIndexOfXisY(3, -1)
    assertIndexOfXisY(9, -1)
    assertIndexOfXisY(11, -1)

module Demo
  public BinarySearch(items : array[int], item : int) : int
    def notFound = -1
    def noMoreItemsToSearch(firstIndex, lastIndex)
      firstIndex > lastIndex
    def isLastItemToSearch(firstIndex, lastIndex)
      firstIndex == lastIndex
    def getPivotIndex(firstIndex, lastIndex)
      (firstIndex + lastIndex) / 2
    def binSearch(firstIndex, lastIndex)
      | range when noMoreItemsToSearch(range) => notFound
      | range when isLastItemToSearch(range) =>
        if(item == items[firstIndex]) firstIndex else notFound
      | range with pivotIndex = getPivotIndex(range) => match(items[pivotIndex])
        | pivot when item < pivot with args = (firstIndex, pivotIndex - 1) \
        | pivot when item > pivot with args = (pivotIndex + 1, lastIndex)  =>
          binSearch(args)
        | _ => pivotIndex

    binSearch(0, items.Length - 1)