smalltalk - 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.

这是我当前的代码，但出现编译错误:“Object: Array new: 4 "<0x7fe20936e940>"error: did not understand #bin:left:right:"。我想知道我做错了什么。

谢谢

Answer 1

第一部分对我来说毫无意义。您的算法是递归的，因此它应该调用自身而不是委托(delegate)给类，这是一个不同的对象。

为此，将 super 替换为 self，然后将使用新参数再次调用相同的方法。

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

进一步说明

1. [ bool 值] ifTrue: 和 friend 的接收者必须是 bool 值(即，true 或 假)。通过将条件括在方括号中，您正在创建一个 BlockClosure。我已经在适当的地方将 [...] 替换为 (...) ，然后在不需要时删除它们(参见下面的 [Precedence])。

2. [比较] 这是有争议的，但是，虽然条件 l==r 并非完全错误，但是，l=r 通常更好。原因:== 的语义对应于完全相同的对象(低级别)，= 的语义等于(或等效)。您的算法不关心 l 和 r 是否由完全相同的对象表示，它只需要知道两个变量是否包含相同的整数。尽管这种区别在这种情况下无关紧要，但您可能会养成使用 == 的习惯，这在您处理其他类型的对象(例如 LargeIntegers 等)的那一天会失败.)

3. [括号] ^ -1不需要加括号

4. [除法] 因为+和/都是消息，所以r中也不需要加括号+ 1/2。但是，除法可能会产生一个 Fraction，而您的代码需要一个 Integer。使用 // 代替获取商数。

5. [冒号] 您忘记了 binSearch 之后的冒号。这会产生 DNU 错误。

6. [Precedence] arr at: iter 周围需要括号，以便将此消息的结果与 val 进行比较(召回优先顺序是:一元、二元、关键字)。

7. [DNU] 关于您收到的错误:您创建的选择器是 binSearch:left:right:，但是您发送了消息 bin :left:right: 未定义。

8. [self] 无需将 self 分配给其他东西:接收者不会随着递归而改变。

9. [Return] 许多 Smalltalkers 应该将返回符号 ^ 移到了最后一个表达式的开头。

10. 在 Smalltalk 中，数组是从 1 开始的，广泛接受的约定是在找不到索引时返回 0(而不是 -1)。

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

---

建议

• 通过添加足够的单元测试来练习和改进您的方法来完成您的工作。我的回答仅限于编码风格，而不是它的正确性。

• 添加以下方法，以便您的服务的客户在使用时无需冗长。

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

• 考虑将选择器更改为更具可读性的内容。您的选择器读起来不是一个句子，而是一种命名参数的方式。怎么样？

binarySearch: value from: left to: right