January 7, 2012
TDD & Binary Search II - A Divide-And-Conquer Test ListStill with the Binary Search problem from the previous blog post. Let's go back to where the problems started:
I think my mistake was to proceed from here in a linear fashion. It is, after all, a divide-and-conquer algorithm. Binary Search works a bit like splitting a deck of cards and then looking at the card there in the middle. if that's not our card, we ask whether our card is higher or lower. If it's higher, we discard the middle card and the bottom of the pack. then we split the top half in the middle, rinse and repeat until the card in the middle is the one we're looking for. (Or we run out of cards.)
So it feels intuitively to me that I should be "splitting the pack" with each new test case, and that, for here on in, we should be finding the number we're searching for.
The simplest implementation I could think of was:
This was encouraging. It's starting to look a bit like the iterative Binary Search algorithm I was going for. We now have this "middle" variable, and we do the comparison there.
Next, I thought, what if our item is not in the middle of the list, but in the middle of the top half of the list?
Which brought me to introduce a movable "bottom" to the array and introduce the loop (since I now had two iterations):
And what about if our item is in the middle of the bottom half of the list?
This test doesn't terminate if you run it with the existing model code, by the way. Just thought I should mention that.
I can pass this test easily by checking if the key is lower than the middle number, and by introducing a movable "top" for the next iteration so we can discard the top half.
Now, I could be wrong - it is late on a Saturday night, and I've been staring at a spreadsheet most of the day - but that's Binary Search, isn't it?
It still feels a little hokey. Especially the leap to iterating. I suspect there are smaller steps in between some of these steps, and will be looking for those next. But the gist of it feels right. The "knack" to test-driving a divide-and-conquer algorithm might be to divide-and-conquer with your tests, rather than follow a naive linear path.
The next big question is: how would I know, if I didn't know I was shooting for a non-linear algorithm, to follow this kind of roadmap?
I think the answer lies in doing some thinking about performamce. If we're looking at potentially larges lists, then a time complexity of O(N) sounds undesirable when N is a big, big number. Basically, we use our experience and a bit of design ken. No surprise there, as that's the key to cracking any problem in software design. There's no algorithm for algorithm design. I might have interspersed these tests with the kind of complexity tests I demonstrated in the previous blog post.
For those of you who favour recursion over iteration, it's a 2 minute job to refactor to:
Good job we wrote those tests, eh?
Posted 7 years, 2 months ago on January 7, 2012