smalltalkgnu-smalltalk

Binary Search in smalltalk


Array extend [
   Array class >> bin: val left: l right: r [
      ^ super binSearch: val left: l right: r
   ]

   binSearch: val left: l right: r [
      |arr iter|
      arr := self.
      [l == r]
         ifTrue: [^ (-1)].
      iter := (r + l)/2.
      [arr at: iter == val]
         ifTrue: [^iter].
      [arr at: iter < val]
         ifTrue:[^ super binSearch val left: l right: iter]
         ifFalse: [^ super binSearch val left: iter right: r]
   ]
]
arr := #(3 6 9 10).
arr bin: 6 left: 1 right: 4.

This is my current code, but I get a compilation error: "Object: Array new: 4 "<0x7fe20936e940>" error: did not understand #bin:left:right:". I was wondering what I was doing wrong.

Thanks


Solution

  • The first part makes no sense to me. Your algorithm is recursive and so it should call itself rather than delegating to the class, which is a different object.

    To do this, replace super with self and the same method will be invoked again with the new parameters.

    Array extend [
       binSearch: val left: l right: r [
          |arr iter|
          arr := self.
          l = r
             ifTrue: [^ -1].
          iter := (r + l) // 2.
          (arr at: iter) = val
             ifTrue: [^iter].
          (arr at: iter) < val
             ifTrue:[^ self binSearch: val left: l right: iter]
             ifFalse: [^ self binSearch: val left: iter right: r]
       ]
    ]
    

    Further remarks

    1. [Boleans] The receiver of ifTrue: & friends must be a Boolean (i.e., true or false). By enclosing the condition between squared brackets you are creating a BlockClosure instead. I've mentally replaced [...] with (...) where appropriate and then removed them whenever they are not required (see [Precedence] below).

    2. [Comparisons] This is debatable but, while the condition l==r is not entirely wrong, however, l=r is generally better. The reason: the semantics of == corresponds to being the very same object (low level), the semantics of = of being equal (or equivalent). Your algorithm doesn't care whether l and r are represented by exactly the very same object, it only needs to know if both variables hold the same integer. Although the distinction is not relevant in this case, you might create an habit of using == which will fail the day you deal with other kinds of objects (v.g. LargeIntegers, etc.)

    3. [Parenthesis] There is no need to add parenthesis to ^ -1.

    4. [Division] Since + and / are messages, there is no need either to add parenthesis in r + 1 / 2. However, the division may produce a Fraction where your code requires an Integer. Use // instead to get the quotient.

    5. [Colons] You had forgotten the colon after binSearch. This creates a DNU error.

    6. [Precedence] Parenthesis are needed around arr at: iter so to compare the result of this message with val (Recall that the precedence order is: unary, binary, keyword).

    7. [DNU] Regarding the error you get: The selector you created is binSearch:left:right:, however you sent the message bin:left:right: which is not defined.

    8. [self] There is no need to assign self to something else: the receiver will not change along the recursion.

    9. [Return] Many Smalltalkers whould have moved the return symbol ^ to the beginning of the last expression.

    10. In Smalltalk, where arrays are 1-based, the convention broadly accepted consists in returning 0 (rather than -1) when no index is found.

    Array extend [
       binSearch: val left: l right: r [
          | iter |
          l = r ifTrue: [^ 0].
          iter := (r + l) // 2.
          (self at: iter) = val ifTrue: [^iter].
          ^ (self at: iter) < val
             ifTrue:[self binSearch: val left: l right: iter]
             ifFalse: [self binSearch: val left: iter right: r]
       ]
    ]
    

    Suggestions

    binSearch: value
      ^self binSearch: value left: 1 right: self size
    
    binarySearch: value from: left to: right