SuperStrict

SeedRnd(0)
' Zahlen Erzeugen:
Const count%=1000
Local Zahl:Int[count]
For Local i:Int = 0 Until count
	Zahl[i]=Rand(1,1000000)
Next
' Sortieren:
Zahl.Sort()

'Find the number:
'815621 ;6493 ;8000 = Y,Y,N
Local number:Int = 8000		'* Die zu findende Zahl
Local val:Int = count *.5	'* Startposition ist die Häfte des Arrays
Local pos:Int = val			'* Position setzen
Local oldpos:Int, nr:Int	'* Veränderung feststellen, Versuche Zählen

Repeat
	nr:+1 '* Neuer Rechenschritt
	Print(nr + ") Zahl[" + pos + "] = " + Zahl[pos])
	
	oldpos = pos '* Alte Position merken
	val:*.5		 '* Hälfte des Ürsprünglichen Arrayteils
	If Zahl[pos] = number Then
		'* Nummer gefunden!
		Print(number + " enthalten!")
		End
	ElseIf Zahl[pos] < number Then
		'* Verschiebe die Position in die eine...
		pos:+val
	Else
		'* ...oder andere Richtung.
		pos:-val
	EndIf
	
Until oldpos = pos '* Val ist so klein, dass keine Änderung mehr statt findet.

Print("Keine "+number+" hier!")
End

SuperStrict

SeedRnd(0)
' Zahlen Erzeugen:
Const count%=1000
Local Zahl:Int[count]
For Local i:Int = 0 Until count
	Zahl[i]=Rand(1, 1000000)
Next
' Sortieren:
Zahl.Sort()

'=======================================================
'Zu Testzwecken wollen wir die Versuche zaehlen,
'die unsere Function find() fuer ihr jeweiliges Resultat braucht:
Global Trials%
'daraus ermitteln wir die maximale Anzahl der Versuche:
Global MaxTrials%
'und ihre Summe, um spaeter die durchschnittliche Anzahl auszurechnen:
Global TrialSum%
'ausserdem - zur Kontrolle - die Anzahl der gefundenen Zahlen:
Local Hits%

'Fuer einen objektiven, zufallsfreien Test,
'muessen wir ALLE Millionen Zahlen suchen lassen:
For Local i% = 1 To 1000000
	Trials = 0
	Local Resultat% = find(i, Zahl)
	If Resultat% > -1 Then
		Hits:+1	
		Print i + " = " + Zahl[Resultat] '(nur zur Kontrolle)
	End If
	TrialSum:+Trials
	MaxTrials = Max(MaxTrials, Trials)
Next
Print Hits + " mal wurde die Zahl gefunden."
Print "Maximale Anzahl an Versuchen: " + MaxTrials
Print "Durchschnittliche Versuchsanzahl: " + (TrialSum / 1000000.0)

'=======================================================
Function find%(Number%, Array%[])
'Falls das Integer-Array die Zahl Number enthaelt,
'wird der entsprechende Index des Arrays returned, ansonsten -1

	'Mit folgenden Variablen wird ein Index-Intervall eingegrenzt,
	'innerhalb dessen ein eventuell passender Arrayeintrag liegt:
	Local MinIndex% = 0
	Local MaxIndex% = Array.length-1
	
	'Die folgende Variable ist ein Index innerhalb dieses Index-Intervalls (und sein Vorgaenger):
	Local Index%, OldIndex%
	
	'Einige Anfangsfaelle werden behandelt: Die gesuchte Zahl ist zu klein oder zu gross:
	If Number < Array[MinIndex] Or Number > Array[MaxIndex] Then Return -1
	'oder die gesuchte Zahl trifft genau auf eine der Intervallgrenzen:
	If Number = Array[MinIndex] Return MinIndex
	If Number = Array[MaxIndex] Return MaxIndex

	'ansonsten liegt sie (eventuell) irgendwo dazwischen: Wir suchen sie,
	'indem wir das Rahmen-Index-Intervall immer weiter verkleinern:	
	Repeat
	
		'Wir koennten nun genau in der Mitte des Intervalls suchen (Bisektion). Da wir aber
		'von einer gleichmaessigen 'linearen Zufallsverteilung' ausgehen, wollen wir die Suche
		'beschleunigen, indem wir den jeweils neuen Index an die Intervall-Arraywerte anpassen:
		
		'So weit liegen die Array-Indizes auseinander:
		Local IndexWidth% = MaxIndex - MinIndex	
		
		'und so weit die dazugehoerigen Werte:
		Local ArrayWidth% = Array[MaxIndex] - Array[MinIndex]
			
		'damit wird ein der gesuchten Zahl angepasster Wert ermittelt:
		Local Value% = IndexWidth * (Number - Array[MinIndex]) / ArrayWidth
		
		'er sollte jedoch nicht direkt auf einer Intervallgrenze liegen:
		Value = Max(1, Min(IndexWidth - 1, Value))
		
		'zum Schluss fuellen wir den neuen Index:	
		Index = MinIndex + Value
		
		'(Zu besagten Testzwecken zaehlen wir die benoetigten Schleifendurchgaenge:)
		Trials:+1

		'Falls wir die gesuchte Zahl direkt getroffen haben, sind wir fertig und
		If Array[Index] = Number Then Return Index 'geben den Index zurueck
		
		'Falls wir feststellen muessen, dass wir ''auf der Stelle treten'',
		If Index = OldIndex Then Return -1 'melden wir unseren Misserfolg

		'Ansonsten merken wir uns den neuen Index
		OldIndex = Index
		
		'und verkleinern das Rahmen-Index-Intervall entsprechend:
		If Array[Index] < Number Then
			MinIndex = Index
		Else	 'If Array[Index] > Number Then
			MaxIndex = Index
		End If
		
	Forever	

End Function