Binary search is not efficient with traversal costs. What is?

Question

Binary search let me down when I tried to apply it to the real world. The scenario is as follows.

I need to test the range of a device that communicates over radio. Communication needs to occur quickly, but slow transmission is tolerable, up to a point (say, about 3 minutes). I need to test whether transmissions will be successful every 200 feet until failure, up to 1600 feet. Every 200 feet a test will be run which requires 3 minutes to execute.

I naively assumed that a binary search would be the most efficient method of finding the failure point, but consider a travel speed of 200 ft/min and test time of 3 minutes. If failure to transmit occurs at 500 feet, binary search is not the most efficient means of finding the failure point, as shown below.

Simply walking along and testing every single point would have found the solution sooner, taking only 12 minutes, whereas binary search & testing would take 16 minutes.

My question: How do you calculate the most efficient path to the solution when traveling time matters? What is this called (e.g., binary-travel search, etc.)?

Answer 1

Binary search is indeed predicated on O(1) access times; there's little point binary searching a linked list, for example [but see Note 1], and that's essentially what you're doing, since you seem to be assuming that only discrete intervals are worth testing. If you were seeking a more accurate answer, you would find that the binary search allows an arbitrary precision, at the cost of one additional test per bit of precision.

Let's suppose you don't know even what the maximum value might be. Then you couldn't first test in the middle, since you wouldn't know where the middle was. Instead, you might do an exponential search for a limit (which is kind of a binary search inside out); you start by testing at x, then 2x, then 4x until you reach a point which is greater than the maximum (the signal doesn't reach that far). (x is the smallest answer you find interesting; in other words, if the first test at x shows the signal doesn't reach, you will then stop.) At the end of this phase, you'll be at 2ix, for some integer i, and you will know the answer is between 2i-1x and 2ix.

Now you can actually do the binary search, starting by going backwards by 2i-2x. From there, you might go either forwards or backwards, but you will definitely travel 2i-3x, and the next iteration you'll travel 2i-4x, and so on.

So in all, in the first phase (search for a maximum), you walked to 2ix, and did i tests. In the second phase, binary refinement, you walk a total of (2i-1-1)x and do i-1 tests. You'll end up at some point d which is between 2i-1 and 2i, so at worst you'll have walked 3d of the final point (and at best, you'll have walked 3d/2). The number of tests you will have done will be 2*ceil(log2(d/x)) - 1, which is within one test of 2*log2(d/x).

Under what circumstances should you do the binary search algorithm, then? Basically, it depends on the ratio of the travel time and the test time, and the desired precision of the answer. The simple sequential algorithm finds position d after d/x moves of size x and d/x tests; the binary search algorithm above finds position d after travelling at most 3d but doing only around 2 log(d/x) tests. Roughly speaking, if a test costs you more than twice the cost of travelling d/x, and the expected distance is sufficiently larger than the precision, you should prefer the binary search.

In your example, you appear to want the result with a precision of 200 feet; the travel time is 1 minute and the test time is 3 minutes, which is more than twice the travel time. So you should prefer the binary search, unless you expect that the answer will be found in a small number of multiples of the precision (as is the case). Note that although the binary algorithm uses four tests and 1000 feet of travel (compared with three tests and 600 feet for the sequential algorithm), improving the precision to 50 feet will only add four more tests and 150 feet of travel to the binary algorithm, while the sequential algorithm will require 20 tests.

---

Note 1: Actually, it might make sense to binary search a linked list, using precisely the above algorithm, if the cost of the test is high. Assuming the cost of the test is not proportional to the index in the list, the complexity of the search will be O(N) for both a lineary search and the binary search, but the binary search will do O(log N) tests and O(N) steps, while the sequential search will do O(N) tests and O(N) steps. For large enough N, this doesn't matter, but for real-world sized N it might matter a lot.