{
  2002 MO P-I-4

  Petr Baudis
  SEPTIMA, gymnazium Ad Fontes Jihlava

  Staci nejakym zpusobem reverzibilne implementovat binarni vyhledavani: pokud
  mame vzestupne setridene pole, koukneme se na jeho prostredni policko.  Bud
  je policko to, co hledame, v tom pripade mame vyhrano. Pokud je hodnota
  policka mensi nez to, co hledame, vime, ze hodnota musi byt v nejakem policku
  v intervalu nad timto polickem, pokud je naopak vetsi, hodnota bude v
  intervalu pod timto polickem. Inu, najdeme si v nem tedy opet prostredni
  policko a takto to opakujeme, dokud to jde. Pokud jiz byl zkoumany interval
  jednopolickovy, v dalsi iteraci se nam meze intervalu prohodi, coz muzeme
  snadno detekovat - tehdy jiz dale nedetekujeme, nic jsme nenasli.

  Postupne se nam vzdy mozny interval zmensi na polovinu, takze casova slozitost
  je prinejhorsim O(log N). Protoze je zde hledani implementovano rekurzivne,
  pri kazdem volani funkce take prijdeme o kousek pameti, pametova slozitost je
  tedy take O(log N).
}

procedure Najdi(var n: word; var X: array [1..n] of word; var co, kde: word)

procedure binarni(var od, do: word)
var stred: word;
begin
  if (od <= do) then
    { Hmm, jeste mame kde hledat.. }
    begin
      wrap
        stred += (od + do) div 2;
      on
        { ..a mame to.. }
	if (X[stred] > co)
          { ..napravo? }
          wrap stred -= 1 on binarni(od, stred, X);
	else if (X[stred < co)
          { ..nebo nalevo? }
          wrap stred -= 1 on binarni(stred, do, X);
	else
          { ..v kapse! }
	  kde += stred;
    end;
end;

begin
  binarni(1, n);
end;