solutions/The Last Algorithms Course You'll Need/5. Two Crystal Balls.c

#include <math.h>
#include <stdio.h>

// complexity is O(sqrt(N))
// well we need ot find an exact moment,
// let's say "height" at which our crystal
// balls break, for that we only have 2 balls,
// so we can't do binary search, since the range
// is tooooo huge, therefore we run a linear
// growth bigger than N, but small enough to find where
// the first ball breaks, then we take the interval
// between: [the previous non-break] and [where it broken]
// and run a normal linear search
// therefore we run sqrt(n) + sqrt(n) times
// so it's O(sqrt(N)

#define SIZE 999

int two_crystal_balls_search(int array[], int size, int value)
{
	int i = 0;
	int step = sqrt((double)(size));
	for (; i < size; i = i + step)
		if (array[i] >= value)
			break;

	printf("Step is: %d\n", step);
	printf("The first one broke at: %d\n", i);

	i = i - step;
	for (; i < i + step; ++i)
		if (array[i] >= value)
			return i;

	return -1;
}

int main()
{
	int array[SIZE];
	for (int i = 0; i < SIZE; ++i)
		array[i] = i;

	printf("The balls break at: %d\n", two_crystal_balls_search(array, SIZE, 567));
}