The Software Purist |

Dec/15

21

Binary Search Part II

A while back (read: years ago), I wrote this post: Software Purist – Binary Search. It wound up being an exercise in algorithm design, along with some interesting points I made about the 80/20 principle and testing. Without looking at what I had done previously, I decided to try to write binary search again. Here’s what I came up with. You should note that this example will use C++11. Here’s the code:

#include <array>
#include <cassert>

using namespace std;

template<class T, class... Tail>
auto make_array(T head, Tail... tail)
  -> std::array<T, 1 + sizeof...(Tail)>
{
	std::array<T, 1 + sizeof...(Tail)> a = { head, tail ... };
	return a;
}

template <class TContainer>
int binarySearch(const TContainer& container,
                 const typename TContainer::value_type& val)
{	
	auto oldBegin = -1;
	auto oldEnd = -1;
	auto begin = 0;
	auto end = container.size() - 1;

	while ((oldBegin != begin || oldEnd != end) && (begin <= end))
	{
		oldBegin = begin;
		oldEnd = end;

 		const auto half = (end - begin + 1) / 2 + begin;
		
		if (container[half] == val)
		{
			return half;
		}
		else if (container[half] < val)
		{
			begin = half + 1;
		}
		else if (container[half] > val)
		{
			end = half - 1;
		}
	}

	return -1;
}

int main()
{
	auto x = make_array(1, 2, 5, 9, 13, 18, 72, 1385);

	assert(binarySearch(x, 0) == -1);
	assert(binarySearch(x, 1) == 0);
	assert(binarySearch(x, 2) == 1);
	assert(binarySearch(x, 3) == -1);
	assert(binarySearch(x, 5) == 2);
	assert(binarySearch(x, 8) == -1);
	assert(binarySearch(x, 9) == 3);
	assert(binarySearch(x, 12) == -1);
	assert(binarySearch(x, 13) == 4);
	assert(binarySearch(x, 15) == -1);
	assert(binarySearch(x, 18) == 5);
	assert(binarySearch(x, 36) == -1);
	assert(binarySearch(x, 72) == 6);
	assert(binarySearch(x, 1000) == -1);
	assert(binarySearch(x, 1385) == 7);
	assert(binarySearch(x, numeric_limits<int>::min()) == -1);
	assert(binarySearch(x, numeric_limits<int>::max()) == -1);
}

It took me a few tries to make it work flawlessly on paper. However, I noticed my test cases were more robust. Obviously, the use of C++11 clouds the issue slightly, as well. I also noted I’m more willing to use int as a data-type now and more likely to use automatic-typing. I’m sure this is due to the influence of other programming languages, like C# and Python. In comparing to the previous, I also noticed better naming, using half rather than newIndex. But, the most striking thing was the fact that my solution was actually different than the previous solution. It encapsulated the same idea, and it’s similar, but not exact. Both solutions work. It’s interesting to see how one’s programming-style evolves ever so slightly (or significantly) over time. It would be hard to say one solution is better than the other.

Going back to the original thought, I still find it amazing that only 10% of programmers get this right. But, as I tried it out on paper, it definitely took me a few goes through my test cases to get it quite right. So, maybe it’s not so far fetched. I think what this is really saying is that 90% of programmers don’t put enough time into unit testing and their test cases. So, let’s discuss that a bit more.

My test cases in this example encompassed all of the following:

  • All values in the array
  • Values not in the array
  • Values not in the array between values that were in the array
  • Negative values
  • Very negative values (checking for underflow)
  • Very large values (checking for overflow)
  • Values less than the minimum value in the array
  • Values larger than the maximum value in the array
  • Zero

If you look at the above, that’s a pretty robust way to approach boundary testing and I encourage you to do the same (where feasible). All of the above can be sources of errors. Also note that sometimes a test case covers multiple conditions, which is great. Just make sure you have a sufficient amount of test cases, to be confident. And then, of course, automate. Normally, one would use a unit test framework, but I wanted to make the code simple enough to run on modern compilers with no additional libraries.

· · ·

No comments yet.

Leave a Reply

<<

>>

Theme Design by devolux.nh2.me