/*

This is yet another explanation of binary search.
However, it works only on array sizes = 2^n

You know, like bank robbers in movies rotating a wheel on a safe (I don't know how it's called correctly)
and find all digits consecutively.
This is like brute-fource.

We do here the same: we try 0/1 for each bit of index value.
We start at 1, and if the array value at this index is too large, we clear the bit to 0 and proceed to the next (lower) bit.

The array here has 32 numbers. The array index has 5 bits ( log2(32)==5 ).
And you can clearly see that one need only 5 steps to find a value in an array of sorted numbers.

The result:

==========================================
testing idx=0x10 or 16
bit 4 is incorrect, it's 0, so we clear it
testing idx=0x8 or 8
bit 3 is correct, it's 1
testing idx=0xc or 12
bit 2 is correct, it's 1
testing idx=0xe or 14
bit 1 is incorrect, it's 0, so we clear it
testing idx=0xd or 13
found, idx=0xd or 13
==========================================

*/

#include <stdlib.h>
#include <stdio.h>

// array of sorted random numbers:
int array[32]=
{
	335, 481, 668, 1169, 1288, 1437, 1485, 1523,
	1839, 2058, 2537, 2585, 2698, 2722, 3245, 3675,
	4067, 4139, 4356, 4599, 5578, 6334, 6751, 7244,
	7845, 8220, 8272, 8296, 8297, 8358, 9138, 9650
};

void binsearch (int val_to_find)
{
	int idx=0;

	for (int bit=4; ; bit--)
	{
		// set the bit:
		idx|=1<<bit;

		printf ("testing idx=0x%x or %d\n", idx, idx);

		if (array[idx]==val_to_find)
		{
			printf ("found, idx=0x%x or %d\n", idx, idx);
			exit(0);
		};

		// array[idx] is too small?
		if (array[idx]<val_to_find)
		{
			// do nothing, the current bit correct, proceed to the next bit
			printf ("bit %d is correct, it's 1\n", bit);
		};

		// array[idx] is too big?
		if (array[idx]>val_to_find)
		{
			// clear the current bit, because it's incorrect
			idx&=~(1<<bit);
			printf ("bit %d is incorrect, it's 0, so we clear it\n", bit);
		};
	};
};

int main()
{
	binsearch(2722);
};