// Podatkovna zbirka: dvojisk.cpp
// Dvojisko ali binarno iskanje v polju
#include <iostream>
#include <iomanip>

using namespace std;

int dvojisko_iskanje(int [], int, int, int, int);

void izpisi_glavo(int);
void izpisi_vrsto(int [], int, int, int, int);

int main()
{
	const int velikost_polja = 15;

	int a[velikost_polja], kljuc, izid;

	for (int i = 0; i < velikost_polja; i++)

		a[i] = 2 * i;   // v polje vstavimo nekaj podatkov

	cout << "Vnesi stevilo med 0 in 28: ";

	cin >> kljuc;

	izpisi_glavo(velikost_polja);
	izid = dvojisko_iskanje(a, kljuc, 0, velikost_polja - 1, velikost_polja);

	if (izid != -1)
		cout << endl << "Stevilo "<< kljuc << " je najdeno v elementu polja "

			  << izid << endl;
	else
		cout << endl << "Stevilo " << kljuc << " ni najdeno." << endl;

    system ("pause");
	return 0;
}

// Dvojisko iskanje
int dvojisko_iskanje(int b[], int iskani_kljuc, int spodnja_meja,

							int zgornja_meja, int velikost)
{
	int srednja_vrednost;

	while (spodnja_meja <= zgornja_meja) {
		srednja_vrednost = (spodnja_meja + zgornja_meja) / 2;

		izpisi_vrsto(b, spodnja_meja, srednja_vrednost, zgornja_meja, velikost);

		if (iskani_kljuc == b[srednja_vrednost])  // zadetek
			return srednja_vrednost;

		else if (iskani_kljuc < b[srednja_vrednost])
			zgornja_meja = srednja_vrednost - 1;   // iskanje v nizjem delu polja


		else
			spodnja_meja = srednja_vrednost + 1;   // iskanje v visjem delu polja

	}

	return -1;   // iskanega kljuca nismo nasli
}

// Izpis glave za izhodne podatke
void izpisi_glavo(int velikost)
{

	cout << endl << "Indeksi:" << endl;

	for (int i = 0; i < velikost; i++)

		cout << setw(3) << i << ' ';

	cout << endl;

	for (int i = 1; i <= 4 * velikost; i++)

		cout << '-';

	cout << endl;
}

// Izpis vrste z delom polja,
// ki je trenutno v obdelavi.

void izpisi_vrsto(int b[], int spodnja_meja, int srednja,

						int zgornja_meja, int velikost)
{
	for (int i = 0; i < velikost; i++)

		if (i < spodnja_meja || i > zgornja_meja)

			cout << "    ";
		else if (i == srednja)

			cout << setw(3) << b[i] << '*';  // oznacitev srednje vrednosti


		else
			cout << setw(3) << b[i] << ' ';

	cout << endl;
}