Reordering sorted array to level-order array without queue

readme.txt

Reordering sorted array to level-order array without queue,
then perform binary search.

http://programmers.stackexchange.com/questions/326301/reordering-sorted-array-to-level-order-array-without-queue

reorder.cc

#include <iostream>
#include <iomanip>

#include <vector>

using size_t = std::size_t;

using Vector = std::vector<size_t>;

using size_type = Vector::size_type;

void reorder(Vector &out, size_t const start, size_t const end, size_t const level, size_t const clevel = 0){
	if (start >= end){
		out.push_back(-1);
		return;
	}

	size_t const mid = start + ((end - start) >> 1);

	if (clevel == level){
		// here we touch the array
		out.push_back(mid);
		return;
	}

	reorder(out, start,   mid, level, clevel + 1);
	reorder(out, mid + 1, end, level, clevel + 1);
}

void reorder(Vector &out, size_t const size, size_t const maxLevels){
	for(size_t level = 0; level < maxLevels; ++level)
		reorder(out, 0, size, level);
}

bool binSearch(const Vector &out, size_t const lookup){
	size_type pos = 0;

	while(pos < out.size()){
		std::cout << "trying pos " << pos << std::endl;

		if (out[pos] == lookup){
			std::cout << lookup << " found on position " << pos << std::endl;
			return true;
		}

		if (lookup < out[pos]){
			// Go left
			pos = 2 * pos + 1;
		}else{
			// Go right
			pos = 2 * pos + 2;
		}
	}

	std::cout << "Not Found" << std::endl;
	return false;
}

int main(){
	size_t const size   = 10;
	size_t const levels = 4;

	Vector out;

	reorder(out, size, levels);

	for(size_type i = 0; i < out.size(); ++ i)
		std::cout
			<< std::setw(4) << i << " "
			<< std::setw(4) << out[i] << std::endl;

	binSearch(out, 3);
}