Binary Search in smalltalk

Question

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

Answer 1

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

• Complete your work by adding sufficient unit tests to exercise and improve your method. I've restricted my answer to the coding style, not its correctness.

• Add the following method so clients of your service don't need to be verbose when using it.

binSearch: value
  ^self binSearch: value left: 1 right: self size

• Consider changing the selector to something more readable. Your selector doesn't read as a sentence, it reads as a way of naming parameters. What about?

binarySearch: value from: left to: right