So, binary search? Why did a new name come up for this well known thing in CS?
I.e. if I asked you to find a squeaky noise coming from somewhere in your house. Does it make sense to "binary search" your 3D 3-story house?
Wolf fencing makes more sense.. stand on floor 2, see if it is on your floor. Or is it coming from the stairwell to floor 3, or the starwell to floor 1? You just used 1 step to narrow your search space down by 1/3.
How would you sort your house so you can binary sort it?
And the bit about cutting the search space to a third (which is what I believe you meant, instead of cutting it /by/ a third) is something you can also do when searching a list, but IIRC halving is preferred because it has better worst-case time-complexity. You can always split a list into 1/3 + 2/3 instead of 1/2 + 1/2, but you risk having to search the 2/3 every time, etc.
As per analogy, you're not checking an animal in Alaska to see if it is a wolf, you are waiting till the wolf howls (side effect of wolf-existence) then focusing your efforts in that area.
So you can't really use wolf-fencing to say... find a number in an array; it makes no sense.
So apply a binary search to an effect instead of a value.
In both cases you could argue that you are "cheating" because there is a computational process of some kind doing at least O(N) work each time (the computer in the debugging example, the universe in the wolf example), giving O(NlnN)+ overall, strictly worse than an O(N) linear search. However, you have to ask yourself in this case if it makes sense to equate the time taken by the computer/universe to run one unit of its computation with the time taken to run one unit of your* search, and in many cases it doesn't. In the end it's just a model and it's up to you to choose what to measure, approximate, and exclude.
If someone tries to argue that there is fundamental philosophical truth that makes one model better than the other, start digging down into the physics of the CPU -- how much O(N^N) quantum computation did the universe have to do in order to bring you a single CPU cycle? God only knows, but the time it takes is nearly constant, so it makes sense to ignore. Even the most hard-core theoretical algorithms expert is just as "guilty" of this kind of approximation as you are :-)
It seems to be used only in the context of debugging. While with git bisect, we are also repeatedly ~halving the remaining search space, the list of commits isn't "sorted" like the precondition for binary search.
You could argue that commits are sorted against time. But I would say that's different because we don't know which commit hash we're looking for -- we just want to find the point in time when our code stopped working, not that I've ever had to use it before ;).
Good point.
One may think that in some sense, it is sorted: The history is sorted into "good" commits (before the bug was introduced), which are followed by "bad" commits (after the bug was introduced).
However, the bisection algorithm also works if "good" and "bad" commits are mixed. Even then it will find one commit where the bug was introduced (although there may be other places where it had been fixed and later reintroduced).
This works because bisection doesn't require a sorted list, it just needs a continuous function. And any sequence is just a special case of that.
I don't understand this comment. Need for sorting the list is essentially the same in both cases, because "the bug was reintroduced" is essentially equivalent to "a lower number showed up later". A binary search makes the assumption of sorting because it's premised on the idea, "Whatever number I find, every number that comes after it will be larger". Same with bug-finding in a git history, it assumes "If I find a point in the history where the problematic behavior exists, it exists at all points after that for the same reason."
If you had an "unsorted" history where a bug was fixed and then reintroduced in another way, your binary search may fail to find the immediate cause of your problems in the same way that an "unsorted" binary search would fail to find what it's looking for.
Yes, and this is perfectly okay for "git bisect".
> Need for sorting the list is essentially the same in both cases.
No, bisection does not require sorting, it just needs a continuous range whose endpoints have different signs. Then, it will always find one point where the signs on both sides differ. (In real analysis, this means finding a zero. In discrete maths, it means find the introduction of a sign change.)
In other words, when starting with a range from an old "good" commit to the current "bad" commit, it will always find a "good" commit directly followed by a "bad" commit.
This is why "bisection" is a good term for this Git algorithm, while "binary search" would be misleading. (Even though bisection and binary search are almost identical algorithms. They mostly differ in their input assumptions and output guarantees.)
Bisection makes no assumtion on any sort order, but guarantees to find one point of bug introduction in logarithmic time. It does not give any guarantee to find the lastest point of bug introduction -- unless, of course, your history does have just one such point.