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.

这是我当前的代码，但出现编译错误：“对象：数组新：4”<0x7fe20936e940>“错误：不理解#bin:left:right:”。我想知道我做错了什么。

谢谢

Answer 1

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

为此，将 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]
   ]
]

进一步说明

[布尔值] ifTrue: 和朋友的接收者必须是 Boolean（即 true 或false)。通过将条件括在方括号中，您创建的是 BlockClosure。我已经在适当的地方将 [...] 替换为 (...)，然后在不需要时删除它们（参见下面的 [Precedence]）。
[比较] 这是值得商榷的，但是，虽然条件 l==r 并非完全错误，但是 l=r 通常是更好的。原因：== 的语义对应于完全相同的对象（低级别），= 的语义等于（或等效）。您的算法不关心 l 和 r 是否由完全相同的对象表示，它只需要知道两个变量是否包含相同的整数。尽管这种区别在这种情况下无关紧要，但您可能会养成使用 == 的习惯，这在您处理其他类型的对象（v.g。LargeIntegers 等）的那一天会失败。
[括号] ^ -1.
不需要加括号
[除] 因为+和/都是消息，所以[=34中也不需要加括号=].但是，除法可能会产生 Fraction，而您的代码需要 Integer。使用 // 来获取商数。
[冒号] 您忘记了 binSearch 之后的冒号。这会产生 DNU 错误。
[Precedence] arr at: iter 周围需要括号，以便将此消息的结果与 val 进行比较（回想一下优先顺序是：一元、二元、关键字）。
[DNU] 关于您收到的错误：您创建的选择器是 binSearch:left:right:，但是您发送的消息是 bin:left:right:未定义。
[self] 无需将 self 赋值给其他东西：接收者不会随着递归而改变。
[Return] 许多 Smalltalkers 应该把 return 符号 ^ 移到最后一个的开头表达式。
在 Smalltalk 中，数组是基于 1 的，广泛接受的约定包括在没有索引时 returning 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

smalltalk 中的二进制搜索

Binary Search in smalltalk

smalltalk

gnu-smalltalk