smalltalk中的二分搜索

html5 • • 问答 

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:”。我想知道我做错了什么。

谢谢

回答

第一部分对我来说毫无意义。你的算法是递归的，所以它应该调用自己而不是委托给类，这是一个不同的对象。

为此，请替换为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. [ Boleas ] ifTrue:&friends的接收者必须是 a Boolean(ie, trueor false)。通过将条件括在方括号之间，您正在创建一个BlockClosure。我已经在适当的地方替换[...]了(...)它们，然后在不需要它们时将其删除（请参阅下面的 [优先级]）。

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

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

  4. [除法] 由于+和/是消息，所以也不需要在 中添加括号r + 1 / 2。但是，除法可能会Fraction在您的代码需要Integer. 使用//代替来获取商。

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

  6. [优先级] 周围需要括号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

  • My pleasure. There are some intellectual rewards in life. Smalltalk is one of them.
以上是smalltalk中的二分搜索的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>