/*
 * Ohjelmoinnin perusteet, syksy 2008, harjoitus 6 (7.-10.10.)
 * Esimerkkiratkaisuja
 * Koostanut Ari Meriläinen
 */
 
 
/* 
 ************************************************************************************  
 ********************************** Tehtävä 24 **************************************
 ************************************************************************************
 * 
 * A.  Laadi yksityisiä luokkametodeja ("pääohjelman pikku apulaisia"), jotka saavat
 *     parametrina taulukko-olion, jonka tyyppi on int[]. Varaudu myös 0:n alkion
 *     mittaisiin taulukoihin. Metodi...
 *       a. asettaa taulukon jokaisen alkion arvoksi indeksin kerrottuna kahdella;
 *          alkioiden arvoiksi tulee tulee siis 0, 2, 4, 6, ...
 *       b. tulostaa taulukon jokaisen alkion, jonka arvo on pariton
 *       c. etsii järjestämättömän taulukon alkioista suurimman ja palauttaa sen
 *          indeksin arvonaan (suurin ei ole välttämättä yksikäsitteinen, miten
 *          etsittäisiin ensimmäinen suurin, entä viimeinen?)
 *       d. siirtää taulukon viimeisen alkion ensimmäiseksi, ensimmäisen toiseksi, toisen
 *          kolmanneksi, jne.; taulukkoa siis "pyöräytetään ympäri" yhden alkion verran.
 *           
 * B. Laadi yksityisiä luokkametodeja ("pääohjelman pikku apulaisia"), jotka saavat
 *    parametrina kokonaislukumatriisin, jonka tyyppi on int[][]. Varaudu myös 0:n alkion
 *    kokoisiin taulukoihin. Metodi...
 *       a. asettaa matriisin jokaisen alkion arvoksi indeksien tulon (esimerkiksi alkio,
 *          jonka indeksit ovat [2][4] saa arvokseen 8)
 *       b. etsii matriisin alkoista pienimmän ja palauttaa sen arvonaan; jos matriisi
 *          sisältää nolla alkiota, metodi palauttaa arvon nolla
 *       c. selvittää, löytyykö parametrina annettu luku matriisista; jos löytyy, metodi
 *          palauttaa arvon true, muuten false 
 *
 */


 
public class Taulukkometodit {
	
	/* *** A) Taulukkoa käsittelevät metodit *** */
	
	/*
	 * a. Metodi asettaa taulukon jokaisen alkion arvoksi indeksin kerrottuna
	 *    kahdella; alkioiden arvoiksi tulee tulee siis 0, 2, 4, 6, ...
	 */
	public static void asetaIndeksiKertaa2(int[] taulu) {
		for (int i=0; i < taulu.length; i++) {
			taulu[i] = i*2;
		}
	}
	
	/*
	 * b. Metodi tulostaa taulukon jokaisen alkion, jonka arvo on pariton.
	 */
	public static void tulostaParittomat(int[] taulu) {
		// Ei tarvita tietoa alkion indeksistä, joten voidaan käyttää for-each -silmukkaa
		for(int alkio : taulu) {
			if (alkio%2 != 0) {
				System.out.println(alkio);
			}
		}
	}
	
	/*
	 * c. Metodi etsii järjestämättömän taulukon alkioista suurimman ja palauttaa sen
	 *    indeksin arvonaan (suurin ei ole välttämättä yksikäsitteinen, miten
	 *    etsittäisiin ensimmäinen suurin, entä viimeinen?)
	 */
	public static int etsiSuurin(int[] taulu) {
		// Jos taulukossa ei ole arvoja, palautetaan -1
		if (taulu.length < 1) {
			return -1;
		}
		int suurimmanIndeksi = 0; // Suurimman toistaiseksi löytyneen alkion indeksi.
		                          // Alkuarvo (0) palautetaan, jos taulukon koko on 1.
		// Silmukkaan mennään vain, jos taulukon koko on suurempi kuin 1.
		for (int i=1; i<taulu.length; i++) {
			// Tutkitaan, onko nykyinen alkio suurempi kuin suurin toistaiseksi löytynyt.
			// Jos taulukossa on useita suurimpia arvoja, tämä vertailu löytää niistä ensimmäisen.
			// Ehto "suurempi tai yhtäsuuri" (>=) löytäisi viimeisen.
			if (taulu[i] > taulu[suurimmanIndeksi]) {
				suurimmanIndeksi = i;
			}
		}
		return suurimmanIndeksi;
	}
	
	/*
	 * d. Metodi siirtää taulukon viimeisen alkion ensimmäiseksi, ensimmäisen toiseksi,
	 *    toisen kolmanneksi, jne.; taulukkoa siis "pyöräytetään ympäri" yhden alkion verran.
	 */
	public static void siirräOikealle(int[] taulu) {
		if (taulu.length > 0) {
			int temp = taulu[taulu.length-1]; // Otetaan viimeinen alkio talteen
		
			// Käydään taulu lopusta alkuun (Mikä ongelma syntyisi, jos käytäisiin alusta loppuun?) 
			for (int i=taulu.length-1; i > 0; i--) {
				taulu[i] = taulu[i-1];
			}
		
			taulu[0] = temp; // Sijoitetaan vanha viimeinen alkio ensimmäiseksi
		}
	}

	/* *** B) Matriisia käsittelevät metodit *** */
	
	/*
	 * a. Metodi asettaa matriisin jokaisen alkion arvoksi indeksien tulon (esimerkiksi
	 *    alkio, jonka indeksit ovat [2][4] saa arvokseen 8)
	 */
	public static void asetaIndeksienTulo(int[][] matriisi) {
		for (int i=0; i<matriisi.length; i++) {
			for (int j=0; j<matriisi[i].length; j++) {
				matriisi[i][j] = i*j;
			}
		}
	}
	
	/*
	 * b. Metodi etsii matriisin alkoista pienimmän ja palauttaa sen arvonaan; jos
	 *    matriisi sisältää nolla alkiota, metodi palauttaa arvon nolla
	 */
	public static int etsiPienin(int[][] matriisi) {
		int pienin = 0; // Pienin löytynyt arvo (alkuarvo 0 palautetaan, jos arvoja ei löydy)
		boolean arvoSaatu = false; // Onko matriisista luettu vielä yhtään arvoa

		// Matriisi on taulukko, jonka alkiot ovat taulukoita (eli tyyppiä int[])
		for(int[] taulu : matriisi) {
			for (int alkio : taulu) {
				// Jos tämä on ensimmäinen saatu arvo, sijoitetaan se pienimmäksi
				if (!arvoSaatu) {
					pienin = alkio;
					arvoSaatu = true;
				}
				// Muuten tarkistetaan, onko alkio pienempi kuin pienin toistaiseksi löytynyt
				else {
					if (alkio < pienin) {
						pienin = alkio;
					}
				}
			}
		}
		return pienin;
	}
	
	/*
	 * c. Metodi selvittää, löytyykö parametrina annettu luku matriisista; jos löytyy,
	 *    metodi palauttaa arvon true, muuten false
	 */
	public static boolean sisältääköLuvun(int[][] matriisi, int etsittävä) {
		// Ei tarvita tietoa alkioiden indekseistä. Käydään vain matriisia läpi ja
		// palautetaan true, jos arvo löytyy.
		for(int[] taulu : matriisi) {
			for (int alkio : taulu) {
				if (alkio == etsittävä) {
					return true;
				}
			}
		}
		// Jos suoritus päätyy tähän, ei alkiota löytynyt
		return false;
	}
	
	/*
	 * Testausta varten apumetodi taulukon arvojen tulostamiseen.
	 */
	private static void tulosta(int[] taulu) {
		for(int alkio : taulu) {
			System.out.print(alkio + " ");
		}
		System.out.println();
	}
	/*
	 * Testausta varten apumetodi matriisin arvojen tulostamiseen.
	 */
	private static void tulosta(int[][] matriisi) {
		for(int[] taulu : matriisi) {
			for (int alkio : taulu) {
				System.out.print(alkio + " ");
			}
			System.out.println();
		}
	}
	
	// Testataan metodeita:
	public static void main(String[] args) {
		System.out.println("A:");
		
		int[] taulu = new int[8]; // Taulukko, jonka kaikki alkiot 0 
		int[] toinenTaulu = { 1, 2, 3, 4, 5, 6, 5, 4, 3, 4, 5, 6 }; // Toinen tapa alustaa taulukko

		tulosta(taulu);
		System.out.println("Asetetaan alkioiden arvoiksi 'indeksi*2')");
		asetaIndeksiKertaa2(taulu);
		tulosta(taulu);
		
		System.out.println("Uusi taulukko:");
		tulosta(toinenTaulu);
		System.out.println("Tulostetaan taulukosta parittomat alkiot:");
		tulostaParittomat(toinenTaulu);
		
		System.out.println("Etsitään suurimman alkion indeksi.");
		int idx = etsiSuurin(toinenTaulu);
		System.out.println("Indeksi: " +idx+". Arvo "+toinenTaulu[idx]);
		
		System.out.println("Siirretään jokaista alkiota pykälä oikealle (viimeinen ensimmäiseksi):");
		siirräOikealle(toinenTaulu);
		tulosta(toinenTaulu);
		
		System.out.println("B:");
		
		int[][] matriisi = new int[3][8]; // 3 riviä, 8 alkiota kussakin
		int[][] toinenMatriisi = { {  1, 2,  3, 4 },
		                           {  2, 3,  4, 5 },
		                           { -3, 4, -5, 6 },
		                           {  4, 5,  6, 7 },
		                           {  5, 6,  7, 8 } };

		System.out.println("Tyhjä matriisi:");
		tulosta(matriisi);
		System.out.println("Asetetaan alkioiden arvoiksi 'rivi-indeksi*sarakeindeksi':");
		asetaIndeksienTulo(matriisi);
		tulosta(matriisi);
		
		System.out.println("Toinen matriisi:");
		tulosta(toinenMatriisi);
		System.out.println("Etsitään sen pienin alkio:");
		int pienin = etsiPienin(toinenMatriisi);
		System.out.println("Pienin oli "+ pienin);
		System.out.println("Tutkitaan, löytyykö matriisista kaivattuja arvoja:");
		System.out.println("Löytyykö -3 : " + sisältääköLuvun(toinenMatriisi, -3));
		System.out.println("Löytyykö 0 : " + sisältääköLuvun(toinenMatriisi, 0));
		System.out.println("Löytyykö 3 : " + sisältääköLuvun(toinenMatriisi, 3));
		System.out.println("Löytyykö 6 : " + sisältääköLuvun(toinenMatriisi, 6));
		System.out.println("Löytyykö 9 : " + sisältääköLuvun(toinenMatriisi, 9));
	}
}

----------------------------------------------

/*
 ************************************************************************************  
 ********************************** Tehtävä 25 **************************************
 ************************************************************************************
 *
 * Tee ohjelma, joka ensin kysyy syötettävien kokonaislukujen lukumäärän, sitten lukee
 * tuon määrän lukuja taulukkoon ja lopuksi tarjoaa seuraavan palvelun: Ohjelmalle
 * annetaan lukuja yksi kerrallaan ja ohjelma selvittää, löytyykö luku taulukosta.
 * Etsimiseen on käytettävä binäärihakua. Muista mitä binäärihaku edellyttää
 * taulukon järjestykseltä!
 *
 */

import java.util.Scanner;

public class EtsintäTaulukosta {
	private static Scanner reader = new Scanner(System.in);
	
	public static void main(String[] args) {
		System.out.print("Kuinka monta lukua haluat syöttää? > ");
		int lukuja = reader.nextInt();
		while (lukuja < 1) {
			System.out.print("Loisin mieluummin taulukon, jossa on lukuja. Eli kuinka monta? > ");
			lukuja = reader.nextInt();
		}
		
		int[] taulukko = new int[lukuja]; // Luodaan taulukko lukuja varten
		
		// Kysytään käyttäjältä luvut taulukkoon
		kysyLuvut(taulukko);
		// Tulostetaan luvut lähinnä testauksen vuoksi
		tulosta(taulukko);
		// Järjestetään luvut nousevaan järjestykseen
		järjestä(taulukko);
		// Tulostetaan taulukko, jotta uskotaan järjestämisalgoritmin toimineen
		tulosta(taulukko);

		/* Binäärihaku siis vaatii järjestetyn aineiston, jotta algoritmi toimisi.
		 * Tässä ratkaisussa luvut kysyttiin ensin ja järjestettiin sitten, mutta
		 * tietysti taulukon järjestyksestä voisi pitää huolta jo lukuja kysyttäessä. */
		
		// Kysellään lukuja ja etsitään niitä annetusta lukujoukosta:
		boolean jatketaan = true; // silmukan lopetusehtomuuttuja
		do {
			System.out.print("Anna syötteistä etsittävä luku (syötä ei-kokonaisluku lopettaaksesi) > ");
			if (reader.hasNextInt()) {
				int luku = reader.nextInt();
				if (binääriHae(luku, taulukko)) {
					System.out.println("Luku löytyi taulukosta!");
				}
				else {
					System.out.println("Lukua ei löydy taulukosta");
				}
			}
			else { // Ei-kokonaisluku lopettaa
				reader.next();
				jatketaan = false;
			}
		} while (jatketaan);
		
		System.out.println("Nähdään!");
	}
	
	/*
	 * Kysyy käyttäjältä kokonaislukuja, kunnes annettu taulukko on täynnä.
	 */
	private static void kysyLuvut(int[] taulu) {
		for (int i=0; i<taulu.length; i++) {
			System.out.print("Anna luku (" + (i+1) + "/" + taulu.length + ") > ");
			taulu[i] = reader.nextInt();
		}
	}

	/*
	 * Järjestää kokonaislukutaulukon alkiot nousevaan järjestykseen.
	 * Järjestämiseen käytetään yksinkertaista vaihtojärjestämistä.
	 */
	private static void järjestä(int[] taulu) {
		for (int i=0; i<taulu.length-1; i++) {
			for (int j=i+1; j<taulu.length; j++) {
				if (taulu[i] > taulu[j]) {
					int apu = taulu[i];
					taulu[i] = taulu[j];
					taulu[j] = apu;
				}
			}
		}
	}
	
	/*
	 * Etsii annettua lukua annetusta taulukosta. Palauttaa true, jos luku löytyy,
	 * tai muutoin false. Etsintä tehdään binäärihaulla, joten taulukon täytyy olla
	 * järjestetty nousevaan järjestykseen.
	 */
	private static boolean binääriHae(int haettava, int[] taulu) {
		int vasen = 0; // Vasen sormi taulukon alkuun
		int oikea = taulu.length-1; // Oikea sormi taulukon loppuun
		while (vasen <= oikea) {
			int keski = (oikea+vasen)/2; // Sormien keskikohta
			if (taulu[keski] == haettava) {
				return true; // Luku löytyi!
			}
			// Jos etsittävä luku keskikohdan oikealla puolella,
			// vasen sormi siirretään pykälää keskikohdasta oikealle
			if (haettava > taulu[keski]) {
				vasen = keski+1;
			}
			// Jos etsittävä luku vasemmalla puolella, oikea sormi
			// siirretään pykälää keskikohdasta vasemmalle
			else {
				oikea = keski-1;
			}
		}
		// Vasen ja oikea sormi menivät ristiin, joten lukua ei löydy:
		return false;
	}
	
	/*
	 * Tulostaa taulukon alkiot.
	 */
	private static void tulosta(int[] taulu) {
		for(int alkio : taulu) {
			System.out.print(alkio + " ");
		}
		System.out.println();
	}
}

----------------------------------------------

/*
 ************************************************************************************  
 ********************************** Tehtävä 26 **************************************
 ************************************************************************************
 *
 * Lotto on numeroveikkaus, jossa arvotaan 7 numeroa ja 3 lisänumeroa 39 numerosta.
 * Loton voittoluokat ovat 7 oikein, 6 ja lisänumero oikein, 6 oikein, 5 oikein ja 
 * 4 oikein. Tee ohjelma joka ensin arpoo oikean lottorivin. Sitten ohjelmalta voi
 * kysellä, onko jokin lottorivi oikein. Kyselyitä voi olla useampia. Suunnittele
 * itse, miten ohjelman toiminta päättyy. Satunnaisluvun väliltä 1-39 saat
 * arvottua vaikkapa seuraavasti:
 *
 *    int arvottu = (int)(39*Math.random()) + 1;
 *
 */


import java.util.Scanner;

public class Lotto {
	// Vakiot määrittelevät, kuinka monta numeroa arvotaan
	private static final int NUMEROITA = 7;
	private static final int LISÄNUMEROITA = 3;
	
	private static Scanner reader = new Scanner(System.in);

	public static void main(String[] args) {
		
		System.out.println("Lottosovellus!");
		System.out.println("Arvotaan "+NUMEROITA+" numeroa ja "+LISÄNUMEROITA+" lisänumeroa");

		int[] numerot = new int[NUMEROITA];
		int[] lisänumerot = new int[LISÄNUMEROITA];
		
		arvoLuvut(numerot, lisänumerot); // Arpoo numerot
		
		// Tulostetaan numerot testauksen vuoksi:
		System.out.print("Numerot: ");
		tulosta(numerot);
		System.out.print("Lisänumerot: ");
		tulosta(lisänumerot);
		
		System.out.println("Lottorivi arvottu. Nyt voit tarkistaa omia rivejäsi.");
		boolean kysyUudestaan = true;
		do {
			int[] omaRivi = new int[NUMEROITA];
			System.out.println("Syötä " + NUMEROITA + " kokonaislukua (väliltä 1-39).");
			for (int i=0; i < omaRivi.length; i++) {
				int numero;
				boolean lukuOk = false;
				do { // Kysytään, kunnes saadaan kelvollinen luku
					System.out.print((i+1) + ". numero > ");
					numero = reader.nextInt();
					if (numero < 1 || numero > 39) {
						System.out.println("Lottonumero voi olla vain väliltä 1-39, syötä uusi.");
					}
					else if (etsiNumero(numero, omaRivi, i)) {
						System.out.println("Rivilläsi oli jo luku " + numero +", syötä uusi.");
					}
					else {
						lukuOk = true;
					}
				} while(!lukuOk);
				
				// Sijoitetaan luku riville
				omaRivi[i] = numero;
			}
			
			System.out.print("Lottorivisi on: ");
			tulosta(omaRivi);
			
			int numeroitaOikein = laskeSamat(omaRivi, numerot);
			int lisäNumeroitaOikein = laskeSamat(omaRivi, lisänumerot);
			
			if (numeroitaOikein == 7) {
				System.out.println("Käsittämätöntä! Sait 7 oikein!");
			}
			else if (numeroitaOikein == 6 && lisäNumeroitaOikein >= 1) {
				System.out.println("6 ja lisänumero oikein! Lähes yhtä käsittämätöntä!");
			}
			else if (numeroitaOikein >= 4) {
				System.out.println("Sait "+numeroitaOikein+" oikein. Rahan tuloa ei voi estää!");
			}
			else {
				System.out.println("Sait "+numeroitaOikein+" numeroa ja "+lisäNumeroitaOikein+
						" lisänumeroa oikein.");
				System.out.println("Harmillisesti et tällä kertaa voittanut mitään.");
			}
			
			System.out.println("Haluatko syöttää uuden rivin? (k/e)");
			String vastaus = reader.next();
			if (vastaus.charAt(0) == 'e') { // Lopetetaan, jos vastaus alkaa e:llä, muuten jatketaan
				kysyUudestaan = false;
			}
		} while(kysyUudestaan);
		
		System.out.println("Nähdään taas!");
	}
	
	/*
	 * Laskee kuinka monta yhteistä numeroa annetuissa taulukoissa on.
	 * (Huom! Ei toimisi oikein, jos tauluissa voisi esiintyä sama luku useaan kertaan,
	 * jonka tämä sovellus muualla estää.)
	 */
	private static int laskeSamat(int[] taulu, int[] taulu2) {
		int samoja = 0;
		for (int i=0; i < taulu.length; i++) {
			for (int j=0; j < taulu2.length; j++) {
				if (taulu[i] == taulu2[j]) {
					samoja++;
				}
			}
		}
		return samoja;
	}
	
	/*
	 * Arpoo kaksi taulukko täyteen lukuja väliltä 1-39 siten, että kukin luku voi
	 * esiintyä korkeintaan kerran jommassa kummassa taulukossa.
	 */
	private static void arvoLuvut(int[] taulu, int[] toinenTaulu) {
		// Täytä ensimmäinen taulukko
		for (int i=0; i<taulu.length; i++) {
			int numero = arvoNumero();
			while (etsiNumero(numero, taulu, i)) { // Numero oli jo arvottu, arvotaan uusi
				System.out.println("Tuli " + numero + ", pitää arpoa uudestaan");
				numero = arvoNumero();
			}
			System.out.println("Arvottiin numero " + numero + " ");
			taulu[i] = numero;
		}
		// Täytä toinen taulukko
		for (int i=0; i<toinenTaulu.length; i++) {
			int numero = arvoNumero();
			// Arvottu numero ei saa esiintyä kummassakaan taulussa
			while (etsiNumero(numero, toinenTaulu, i) || etsiNumero(numero, taulu, taulu.length)) {
				System.out.println("Tuli " + numero + ", pitää arpoa uudestaan");
				numero = arvoNumero();
			}
			System.out.println("Arvottiin numero " + numero + " ");
			toinenTaulu[i] = numero;
		}
	}

	/*
	 * Arpoo kokonaisluvun väliltä 1-39
	 */
	private static int arvoNumero() {
		return (int)(39*Math.random()) + 1;
	}
	
	/*
	 * Etsii tiettyä numeroa annetusta taulukosta. Taulukkoa ei kuitenkaan tutkita
	 * kuin korkeintaan indeksiin 'loppuIndeksi-1' asti. (Koska se sattuu tässä
	 * tehtävässä olemaan järkevää)
	 */
	private static boolean etsiNumero(int etsittävä, int[] taulukko, int loppuIndeksi) {
		// Katsotaan lopetetaanko tutkiminen loppuIndeksiin vai taulukon loppuun		
		int loppu = Math.min(taulukko.length, loppuIndeksi);
		
		for (int i=0; i<loppu; i++) {
			if (taulukko[i] == etsittävä) {
				return true;
			}
		}
		return false;
	}
	
	/*
	 * Tulostaa taulukon alkiot.
	 */
	private static void tulosta(int[] taulu) {
		for (int alkio : taulu) {
			System.out.print(alkio + " ");
		}
		System.out.println();
	}
}

----------------------------------------------

/*
 ************************************************************************************  
 ********************************** Tehtävä 27 **************************************
 ************************************************************************************
 *
 * Tee sovellus, joka tulostaa komentoriviparametrit String-vertailujen antamassa
 * "aakkosjärjestyksessä".
 *
 */

public class TulostaParametrit {
	public static void main(String[] args) {
		if (args.length >= 1) {
			// Järjestä komentoriviparametrit..
			lisäysJärjestä(args);
			// ..ja tulosta ne
			for (String s : args) {
				System.out.println(s);
			}
		}
		else {
			System.out.println("Ole hyvä ja anna joitain komentoriviparametreja.");
		}
	}
	
	/*
	 * Järjestää String-taulukon nousevaan järjestykseen lisäysjärjestämisalgoritmia
	 * käyttäen.
	 */
	public static void lisäysJärjestä(String[] taulu) {
		for (int i=1; i<taulu.length; i++) {
			String alkio = taulu[i];
			int j=i;
			while (j > 0 && alkio.compareTo(taulu[j-1]) < 0) {
				taulu[j] = taulu[j-1];
				j--;
			}
			taulu[j] = alkio;
		}
	}
}

/*
 ************************************************************************************  
 ********************************** Tehtävä 28 **************************************
 ************************************************************************************

 "Vertaile peräkkäishakua ja binäärihakua järjestetystä taulukosta. Kuinka monta alkiota
  joudutaan tutkimaan helpoimmassa ja vaikeimmassa tapauksessa kun taulukon koko on 10,
  100, 1000, 10000, 100000 alkiota? Löydätkö yleistä kaavaa vaikeimmalle tapaukselle?
  Osaatko arvioida, montako alkiota keskimäärin joudutaan tutkimaan?"

 

Peräkkäishaussa helpoin tapaus on tietysti aina se, jossa etsittävä arvo on taulukossa
ensimmäisenä. Vaikeimmassa tapauksessa taas kaikki taulukon alkiot on käytävä läpi,
ennen kuin tulos selviää. Tämä voi tarkoittaa joko sitä, että haettu arvo on taulukon
viimeinen alkio, tai että se on arvo, jota taulukosta ei löydy, ja myös suurempi kuin
taulukon suurin arvo. Jos etsittäisiin arvoa, jota taulukossa ei ole, mutta se olisi
pienempi kuin taulukon suurin arvo, peräkkäishaun voisi lopettaa heti, kun ohitetaan
se paikka, johon etsittävä arvo taulukossa kuuluisi.

Yleinen kaava peräkkäishaun vaikeimmalle tapaukselle on siis yksinkertaisesti
"n, missä n=taulukon koko". Ja koska helpoin tapaus on aina 1 ja vaikein aina n,
lienee keskimääräinen tapaus n/2.

Binäärihaussakin etsittävä löytyy helpoimmassa tapauksessa ensimmäisestä tutkitusta
paikasta, eli taulukon puolivälistä. Binäärihaku ei kuitenkaan pahimmassa tapauksessa joudu
käymään läpi lähellekään samanlaista määrää alkioita kuin peräkkäishaku. Jokaisella
ohi menneellä yrityksellä binäärihaku voi eliminoida puolet jäljellä olevista alkioista.
Esimerkiksi 1000 alkion taulusta binäärihaku etenisi pahimmassa tapauksessa tähän tapaan:
 
 1. yritys : 500 mahdollista jäljellä
 2. yritys : 250 mahdollista jäljellä
 3. yritys : 125 mahdollista jäljellä
 4. yritys : 62 mahdollista jäljellä
 5. yritys : 31 mahdollista jäljellä
 6. yritys : 15 mahdollista jäljellä
 7. yritys : 7 mahdollista jäljellä
 8. yritys : 3 mahdollista jäljellä
 9. yritys : 1 mahdollinen jäljellä
10. yritys : haettava löytyi TAI tiedetään, ettei haettavaa ole taulukossa

Koska hakualue puoliintuu joka kierroksella, voidaan ajatella jokaisen yrityksen
osumatodennäköisyyden siis olevan kaksinkertainen. Näin voimme junailla etsinnälle
kaavan 2^t=n, missä t on tarvittavien yritysten määrä ja n taulukon koko. Tästä 't'
selviää pyöräyttämällä kaava muotoon t=lb(n) (lb tarkoittakoon kaksikantaista
logaritmia). Tulokseksi ei tietenkään aina tule kokonaislukua, ja intuitiivisesti
lienee ymmärrettävää, että tulos (eli yritysten määrä) täytyykin pyöristää ylöspäin
lähimpään kokonaislukuun. Täten pahimman tapauksen kaava on siis ceil(lb(n)).

Keskimääräinen tapaus on binäärihaussa hyvin lähellä pahinta tapausta. Jos palataan tuohon
kaavaan 2^t=n, niin huomataan, että 2^(t-1) = (n/2). Eli jos 't' yrityksellä saadaan
tutkittua joka ainoa taulukon alkio, niin t-1 yrityksellä saadaan tutkittua vain puolet.
Todennäköisyyslaskenta sanonee, että on noin 50% mahdollisuus, että mielivaltainen
kaivattu alkio on juuri siinä puolikkaassa, jota ei vielä ole tutkittu. Siispä binäärihaun
keskimääräisen tapauksen kaava on lb(n)-1 (tässä ei tarvita pyöristystä ylöspäin).

Teorian mukaan binäärihaku vaatisi taulukoista seuraavanlaisia hakumääriä:
Taulukon koko     10    100    1000   10000   100000
Pahin tapaus       4      7      10      14       17
Keskimääräinen  2,32   5,64    8,97   12,29    15,61

Mutta onneksi näissä asioissa ei tarvitse turvautua vain matematiikkaan. On tunnetusti
aina hauskaa ja jännittävää tehdä hieman empiiristä tutkimusta ohjelmoiden! Vaikkapa
seuraavanlaisen koodinpätkän avulla:

(Huomautettakoon, että ratkaisussa tulostukseen käytettyä System.out.format()-metodia
ei kuulukaan vielä osata!)

*/

public class BinäärihakuTutkimus {

	public static void main(String[] args) {
		final int TOISTOJA = 1000; // Montako kertaa haku toistetaan
		
		// Käydään läpi taulukon koot 10, 100, 1000, 10000 ja 100000
		for (int i=1; i<=5; i++) {
			int koko = (int)Math.pow(10, i); // 10 potenssiin i
			System.out.println("Taulukon koko "+koko);
			int[] taulu = new int[koko];
			luoTaulu(taulu); // Alustetaan taulu alkioilla 1-koko
			int haettava = koko+1; // Luku, jota taulusta ei löydy
			etsi(haettava, taulu);

			// Toistetaan hakuja satunnaisilla luvuilla:
			toistaHaku(taulu, TOISTOJA);
			// Ja vielä verrokkina teorian antamat tulokset:
			System.out.format("Kaksikantainen logaritmi %d = %.2f (pahin tapaus)\n",
					koko, Math.log10(koko)/Math.log10(2));
			System.out.format("Kaksikantainen logaritmi %.1f = %.2f (keskimääräinen tapaus)\n",
					koko/2.0, Math.log10(koko/2.0)/Math.log10(2));
			System.out.println();
		}
	}
	
	/*
	 * Suorittaa annetun määrän binäärihakuja annetusta taulusta arvotuilla luvuilla.
	 */
	private static void toistaHaku(int[] taulu, int kertoja) {
		int summa = 0;
		for (int i=0; i<kertoja; i++) {
			// Arvotaan etsittävä luku väliltä 1-taulukon koko
			int haettava = (int)(Math.random()*taulu.length) + 1; 
			int tulos = binääriHae(haettava, taulu);
			if (tulos < 0) {
				summa -= tulos;
			}
			else {
				summa += tulos;
			}
		}
		double keskiarvo = 1.0*summa/kertoja;
		System.out.format("Etsittiin %d alkion taulusta %d kertaa. Keskimäärin tarvittiin %.1f hakua.\n",
				taulu.length, kertoja, keskiarvo);
	}
	
	/*
	 * Etsii annettua lukua annetusta taulukosta käyttäen binäärihakua, ja tulostaa viestin
	 * haun onnistumisesta.
	 */
	private static void etsi(int haettava, int[] taulu) {
		int tulos = binääriHae(haettava, taulu);
		if (tulos > 0) {
			System.out.format("%d alkion taulusta luku %d löytyi %d haun jälkeen\n",
					taulu.length, haettava, tulos);
		}
		else {
			System.out.format("%d alkion taulusta tarvittiin %d hakua, jotta havaittiin, ettei lukua %d löydy\n",
					taulu.length, (-1*tulos), haettava);
		}
	}
	
	/*
	 * Etsii haluttua kokonaislukua annetusta taulukosta käyttäen binäärihakua, ja palauttaa
	 * tiedon tarvituista hakuyrityksistä. Jos alkio löytyi, metodi palauttaa yritysten määrän.
	 * Jos alkiota ei löytynyt, metodi palauttaa yritysten määrän käänteisluvun.
	 */
	private static int binääriHae(int haettava, int taulu[]) {
		int vasen = 0;
		int oikea = taulu.length-1;
		int keski = (vasen+oikea)/2;
		int hakuja = 0;
		while (vasen <= oikea) {
			hakuja++;
			if (taulu[keski] == haettava) {
				return hakuja; // Löytyi!
			}
			if (haettava < taulu[keski]) {
				oikea = keski-1;
			}
			else if (haettava > taulu[keski]) {
				vasen = keski+1;
			}
			keski = (vasen+oikea)/2;
		}
		// Ei löytynyt
		return -1*hakuja;
	}

	/*
	 * Alustaa annetun taulukon arvoilla siten, että kunkin alkion arvoksi tulee indeksi+1.
	 */
	private static void luoTaulu(int[] taulu) {
		for (int i=0; i<taulu.length; i++) {
			taulu[i] = i+1;
		}
	}
}