(* Recherche dichotomique dans une liste triée *)

#open "sort";;
#open "random";;
init (int_of_float (sys__time()));;

let rec cree_hasard max=fun
	|0->[]
	|n->(int max)::cree_hasard max (n-1) 
 ;;

cree_hasard 100 50;;

let tab_has=vect_of_list (sort  (prefix <) (cree_hasard 1000 500));;

(* ci-dessous une belle erreur bien perfide! *)
let cherche n liste=
	let rec essaye min max=
		print_string "min :   ";print_int min;
		print_string "max :   ";print_int max;print_newline();
		let milieu=liste.((min+max)/2) in
		if min=max 
		then 	if n=liste.(min)
			then print_string "gagné"		
			else print_string "perdu"
		else 	if n>liste.((min+max)/2) 
			then essaye ((min+max)/2) max
			else essaye min ((min+max)/2) 
	in essaye 0 (vect_length liste -1)
;;
		

let cherche n liste=
	let rec essaye min max=
		print_string "min :   ";print_int min;
		print_string "   max :   ";print_int max;print_newline();
		let milieu=liste.((min+max)/2) in
		if min>=max -1
		then 	if (n=liste.(min) or n =liste.(max))
			then print_string "gagné"		
			else print_string "perdu"
		else 	if n>liste.((min+max)/2) 
			then essaye ((min+max)/2) max
			else essaye min ((min+max)/2) 
	in essaye 0 (vect_length liste -1)
;;