Chapter 21 Exercise 7

[chrinkus]

Chapter 21 Exercise 7

[Chrinkus]

I agree a binary search through a linked-list is a rare occurrence but it wasn't always. Modern CPUs are blazing fast at working with contiguous data so even the use-case of "many insertion, deletions" of a linked list doesn't apply anymore. Twenty years ago you would definitely see more lists in use.

The exercise was more to encourage you to create an algorithm that could be applied to different generic containers. So were you able to write two binary search functions that only differed in the types they worked on?

Programming for me is a side thing that keeps getting pushed further aside by the new demands of my changing job. I hope to pick it up again going into Christmas break and keep up with it.

[Josh1603]

Here's what I wrote. It's a recursive binary search function for containers with random access iterators:

// Only really seems to make sense with sorted containers which have random access interators. 
// As there don't appear to be many might be better to simply provide specialisations for those cases with generalised elem?
// Or could concepts be used to ensure user only used this template method when a sorted collection with a random access iterator is used?

// This works because end is either never checked (when it remains as end of sequence for entire recursion) or it is first checked as middle before becoming a new end.
// It's important to keep the end member of the sequence redundant in this way for each iteration, as the initial sequence provides a redundancy and recursion requires consistency.
template <typename T, typename Iter>
bool my_binary_search(Iter begin, Iter end, T& val) {

	auto middle = begin + ((end - begin) / 2); //Get an itertator to the middle position using pointer arithmetic. Favours begin's side over end to help prevent possibility of derefencing the end of sequence.

	if (*middle == val)
		return true;
	if (middle - begin > 0 || end - middle > 1)  //Check to see if there's anything left to search. (End is either end of sequence or already checked as previous middle and current middle was already checked hence > 1) 
		return (*middle > val) ? my_binary_search(begin, middle, val) : my_binary_search(middle, end, val); //Recursively call function with the section of the sequence which could hold the value
	return false;
}

I'm currently attempting to develop a simple cross-platform mobile game in C++. I've had a few hitches with the game engine I'm using, but it's great to be able to apply some of these skills on a practical project!