Compiler Explorer

Source code

import std.format;
import std.math.exponential;
import std.math.rounding;
import std.range;
import std.stdio;
import std.traits;

int bsearch1000(ref int[1001] xs, int x)
{
	auto i = 0;
	if (xs[512] <= x) { i = 1000 - 512 + 1; }
	if (xs[i+256] <= x) { i += 256; }
	if (xs[i+128] <= x) { i += 128; }
	if (xs[i+64] <= x) { i += 64; }
	if (xs[i+32] <= x) { i += 32; }
	if (xs[i+16] <= x) { i += 16; }
	if (xs[i+8] <= x) { i += 8; }
	if (xs[i+4] <= x) { i += 4; }
	if (xs[i+2] <= x) { i += 2; }
	if (xs[i+1] <= x) { i += 1; }
	
	if (xs[i] == x) return i;
	else return 0;
}

auto iflog2(int n) => cast(int) floor(log2(n));

auto bsearch(T, size_t n)(ref T[n] xs, T x)
{
	writeln("static array");

enum k = iflog2(n - 1);
	writeln("k = ", k);
	auto p = 0;

if (xs[2 ^^ k] <= x) p = (n - 1) - (2 ^^ k) + 1;

static foreach_reverse (int i; 0 .. k)
	{
		if (xs[p + 2 ^^ i] <= x) p += 2 ^^ i;
	}

if (p > 0 && xs[p] == x) return p;
	return 0;
}

auto bsearch(T)(T[] xs, T x)
{
	writeln("dynamic array");
	auto n = cast(int) xs.length;
	auto k = iflog2(n - 1);
	auto p = 0;

if (xs[2 ^^ k] <= x) p = (n - 1) - (2 ^^ k) + 1;

foreach_reverse (int i; 0 .. k)
	{
		if (xs[p + 2 ^^ i] <= x) p += 2 ^^ i;
	}

if (p > 0 && xs[p] == x) return p;
	return 0;
}

void main()
{
	int[9] es = [0, 1, 2, 2, 2, 2, 2, 2, 2];
	writeln(bsearch(es, 2));

int[1001] xs;
	int[] dxs;
	dxs.length = 1001;

for (auto i = 1; i <= 1000; i++) {
		xs[i] = i * 2;
		dxs[i] = i * 2;
	}
	writeln(bsearch(xs, 1000));
	writeln(bsearch(dxs, 1000));
}