调试和二进制搜索 [英] Debugging and Binary Search

问题描述

第2栏（AHA！Algorithm）中的编程珍珠介绍了二进制搜索如何排序，树遍历等各种过程。但是它提到二进制seach可以在程序调试中使用。有人可以解释一下这个问题吗？

解决方案

另一个可能性是你有一个错误，你知道这不是在你的二月发行版中，但是在4月份的版本中（或者说是你的4月发行版本的候选人），你永远不会向你的用户发送错误，对吧？）。

您可以通过修订版本控制历史来进行手动二进制搜索，以缩小错误的时间。首先检查两个版本之间的代码，构建它，并查看该bug是否存在。继续分割，直到你知道什么时候被介绍。如果你不知道从哪里开始寻找这个bug，这可能是非常有效的，特别是如果你做的很小的提交。

这个工作非常好用 Subversion ，因为它具有版本库版本号。如果您的二月份版本为533，而您的4月发行版本为701，那么您更新到617号，测试它，然后从那里转到。 （实际上，我通常是600，所以我不必这么做数学。）一旦我开始把它缩小了，我就开始看看提交的评论，并做出有教养的猜测（我真的不认为这个提交会破坏它），所以我通常不需要做所有的log ₂ （n）检出。

我'从来没有使用过 Git ，但是他们采用了内置的 bisect 命令。你给它一个起点（什么时候知道工作？）和结束点（你什么时候注意到它被打破了），它将自动获得二进制搜索中的中间点的代码。然后在你建立和测试后，你告诉它是否通过或失败;那么它将获得下一个中间点的代码。您甚至可以告诉它为每个rev运行命令，并使用命令的退出代码来确定rev是否通过或失败，此时它可以全自动运行。

"Programming Pearls" in the column 2 ("AHA! Algorithm") talks about how binary search aids in various processes like sorting, tree traversals. But it mentions that binary seach can be used in "program debugging". Can somebody please explain how this is done?

解决方案

Another possibility is that you have a bug, and you know it wasn't there in your February release, but it was in your April release (or rather, your April release candidate -- you would never actually ship a bug to your users, right?).

You can do a manual binary search through your revision-control history to narrow down when the bug was introduced. First check out the code halfway between the two releases, build it, and see if the bug is there. Keep partitioning until you find out when it was introduced. If you don't know where to start looking for the bug, this can be very effective, especially if you do fairly small commits.

This works very well with Subversion because it has repository-wide revision numbers. If your February release was rev 533 and your April release was rev 701, then you update to rev 617, test it, and go from there. (Actually, I usually round to 600 so I don't have to do so much math in my head.) Once I start to narrow it down, I start looking at the commit comments and making educated guesses ("I really don't think this commit would have broken it"), so I usually don't need to do all log₂(n) checkouts.

I've never used Git, but they take this one step further with the built-in "bisect" command. You give it a starting point (when was it known to work?) and ending point (when did you notice it was broken?), and it will automatically get the code for the halfway point in the binary search. Then after you've built and tested, you tell it whether this rev passed or failed; then it gets the code for the next halfway point. You can even tell it to run a command for each rev and use the command's exit code to determine whether the rev is a pass or fail, at which point it can run on full automatic.

这篇关于调试和二进制搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！