Hey, this is the proof that I developed this algorithm (test4 (most important one) and all others):

(@ Google Stuff: If you like this and are looking for a developer: I am still freely aviable when you pay well.)

package uni.zwo.aud;

import java.awt.Color;
import java.awt.Graphics;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.Arrays;

import javax.imageio.ImageIO;

public class HälfteIdentisch {

static void test2(){
int min = 1024, fh = 0;
int l = 1024;
Obj[] werte = new Obj[l];
for(int k=0;k<100000;k++){// 9 / 100k sind falsch
double r = Math.random();
int cx = 0;
for(int i=0;i<l;i++){
if(Math.random() > r){
werte[i] = new Obj(0);// Objekte, die gleich sein können
cx++;
} else werte[i] = new Obj((int)(Math.random()9)+1);// andere/
}
if(hälfteOknlogn2(werte, l)){
if(cx < min){
if(cx <= l/2){
System.out.println(cx+" = ");
for(int i=0;i<l;i++){
System.out.print(werte[i].value);
}System.out.println();
}
min = cx;
}
} else if(cx>l/2){
fh++;
}
}

for(int i=0;i<l;i++){
System.out.print(werte[i].value);
}System.out.println();

System.out.println(min+" und "+fh+" Fehler.");
}

static void test1(){
/*// 1. Sortierversuch
int gutindex = 0;
for(int i=0;i<l-2;i++){
if(werte[i] == werte[i+1]){
// nichts
} else {
if(werte[i] == werte[i+2]){// A bzw C ist ein Kandidat für den Erfolgreichen, maximal gibt es davon 50% Stück
// B <-> C
int k = werte[i+1];
werte[i+1] = werte[i+2];
werte[i+2] = k;

gut[gutindex++] = werte[i];
// C!=B ->
i++;
}// else nichts
}
}

for(int i=0;i<l;i++){
System.out.print(werte[i]);
}System.out.println();*/

System.out.println();
}

public static void main(String[] args) throws IOException {
test4();
}

static void test3() throws IOException {

BufferedImage img = new BufferedImage(100, 2000, 1);
Graphics g = img.getGraphics();
g.setColor(Color.RED);
for(int l=0;l<20;l++){
System.out.println(l);
int s = (l+1) * 300;
for(int j=0;j<20;j++){
double chance = j/19.;
int[] d = new int[s];
double mult = 9/(1-chance);
for(int k=0;k<100;k++){
for(int i=0;i<s;i++){
double r = Math.random();
if(r < chance){
d[i] = 0;
} else {
d[i] = (int) ((r - chance) * mult) + 1;
}
}
if(hälfteOkRandom(d, s)){
g.fillRect(j*5, k + l*100, 5, 1);
}
}
}
}

g.dispose();
ImageIO.write(img, "png", new File("/home/antonio/test3.png"));

int s = 10000;
System.out.println(check3(s, .48)+" / s-"+(s-check3(s, .52))+" for int["+s+"]");
}

static void test4(){
/*int gx = 0, ts = 10000;
for(int j=0;j<ts;j++){
int l = 10000, cx = 0;
int[] werte = new int[l];
double chance = .7, mult = 10000/(1-chance);
for(int i=0;i<l;i++){
double r = Math.random();
if(r < chance){
werte[i] = 0;// Objekte, die gleich sein können
cx++;
} else werte[i] = (int)(r * mult)+1;// andere
}
if(hM(werte, werte.length) == (cx > l/2)){
gx++;
}
}

System.out.println(gx+" / "+ts);*/
/*BufferedImage img = new BufferedImage(1000, 1000, 1);
Graphics g = img.getGraphics();
for(int j=1000;j>0;j--){

int size = j * 1000;
int[] data = new int[size];
double chance = .5;
for(int i=0;i<size;i++){
double r = Math.random();
if(r < chance){
data[i] = 0;// Objekte, die gleich sein können
} else data[i] = (int)((r-chance) * 18)+1;// andere
}
ctr = 0;
long t = System.nanoTime();

hM(data, size);

t = System.nanoTime()-t;

System.out.println(ctr);// 19871550

g.fillRect(j-1, 1000-(int) (ctr/2000), 1, (int) (ctr/2000));

}
g.dispose();
try {
ImageIO.write(img, "png", new File("/home/antonio/test4.png"));
} catch (IOException e) {
e.printStackTrace();
}*/
}

static int hMWert;
static int var;
static boolean hM(int[] werte, int l){
hMS(werte, 0, l);
if(hMWert > -1){// !=null
int c = 0;
for(int i=0;i<l;i++){
if(werte[i] == hMWert) c++;
}
return c > l/2;
} else return false;
}
static int ctr;
static void hMS(int[] werte, int start, int l){
ctr++;
if(l==1){
// A / B
hMWert = werte[start];
var = 0;
} else {
// ABAA
int hm1, hm2, var1, var2, lf2 = l/2;
hMS(werte, start, lf2);
hm1 = hMWert;
var1 = var;
hMS(werte, start+lf2, l-lf2);
hm2 = hMWert;
var2 = var;
if(hm1!=hm2){
var = var1 + var2 + 1;
if(hm1 < 0){// hm1 ist null
hMWert = hm2;
} else if(hm2 < 0){// hm2 ist null
hMWert = hm1;
} else if(var1 > var2){
hMWert = hm2;
} else if(var2 > var1){
hMWert = hm1;
} else {
// weder hm1 noch hm2 sind null, doch beide sind verschieden; vielleicht sollte ich einfach
// den mit geringerer Varianz überleben lassen
hMWert = -1;//null
}
}// else Varianz bleibt und Wert bleibt
}

//System.out.println(start+"-"+(start+l)+" ret\t"+hMWert+"("+var+")");

}



static int check3(int s, double chance){
double mult = 9/(1-chance);
int[] d = new int[s];
for(int i=0;i<s;i++){
double r = Math.random();
if(r < chance) d[i] = 0;
else d[i] = (int) ((r - chance) * mult) + 1;
}
int ok=0;
for(int i=0;i<10000;i++){// 837, 833
// 100 Tests um herauszufinden, wie toll der Algorithmus ist...
if(hälfteOkRandom(d, s)){
ok++;
}
}
return ok;
}

static int counta = 0;

static boolean hälfteOkRandom(int[] werte, int l){

int ok = 0, tests = (int) (5 * Math.sqrt(l));

for(int i=0;i<tests;i++){
if(werte[(int) (Math.random()*l)] == werte[(int) (Math.random()*l)]){
ok ++;
}
}
return ok > tests * .2779;// .28 = 38/1130, .2785 = 34/325, .278 = 148/231, .2779 = 43(1217/226)/187(153/46), .277 = 1162/107, .27 = 4454/44

}

static boolean hälfteOknlogn2(Obj[] werte, int l){
Obj x = hälfteOknlogn2Biggest(werte, 0, l-1);
return x!=null;
}

static Obj hälfteOknlogn2Biggest(Obj[] werte, int start, int ende){
// finde den häufigsten von start bis ende
if(start < ende){
// 3er Auswertung?
int t1 = (2*start+ende)/3, t2 = (2*ende+start)/3;
Obj v0 = hälfteOknlogn2Biggest(werte, start, t1),
v1 = hälfteOknlogn2Biggest(werte, t1+1, t2),
v2 = hälfteOknlogn2Biggest(werte, t2+1, ende);
if(v0!=null && (v0.equals(v1) || v0.equals(v2))){
return v0;
} else if(v1!=null && (v1.equals(v2))){
return v1;
} else return null;
/*int t1 = (start+ende)/2;
Obj v0 = hälfteOknlogn2Biggest(werte, start, t1),
v1 = hälfteOknlogn2Biggest(werte, t1+1, ende);
System.out.println(v0+" "+v1+" bei "+start+" - "+ende+"");
if(v0==null || !v0.equals(v1)) return null;
return v0;*/
} else {
return werte[start];
}
}

static class Obj {
private int value;
public Obj(int value){
this.value = value;
}

public boolean equals(Obj o){
return o==null?false:o.value == value;
}

public String toString(){
return value+"";
}
}

static boolean hälfteOknlogn(int[] werte, int l){
int[] copy = Arrays.copyOf(werte, l);
if(hälfteOknlognPart(werte, l)){
int ok = 0;
for(int i=0;i<l;i++){
if(copy[i] == werte[0]){
counta++;
ok ++;
}
}
System.out.println(ok+" / "+l+" (Wert: "+werte[0]+")");
return ok > l/2;
}
return false;
}

static boolean hälfteOknlognPart(int[] werte, int l){
// 1. Sortierversuch
int gutindex = 0;
for(int i=0;i<l-2;i++){
counta++;
if(werte[i] == werte[i+1]){
//werte[gutindex++] = werte[i];
// nichts
} else {
counta++;
if(werte[i] == werte[i+2]){// A bzw C ist ein Kandidat für den Erfolgreichen, maximal gibt es davon 50% Stück
// B <-> C
int k = werte[i+1];
werte[i+1] = werte[i+2];
werte[i+2] = k;

// werte[gutindex] kann ich überschreiben, da wir uns es nicht mehr ansehen werden (gutindex <= i)
werte[gutindex++] = werte[i];
// C!=B ->
i++;
}// else nichts
}
}

for(int i=0;i<gutindex;i++){
System.out.print(werte[i]);
}System.out.println();
System.out.println(gutindex+" / "+l);

if(gutindex==0){
// es kann auch alles eindeutig gewesen sein...
// werte ist noch das Originalarray
int start = werte[0];
for(int i=1;i<l;i++){
counta++;
if(start != werte[i]){
// keine doppelten trotz verschiedenen...
System.out.println("Problemzeile?:");
for(int j=0;j<l;j++){
System.out.print(werte[j]);
}System.out.println();
return false;
}
}
return true;// alles ist vom gleichem Typ
} else if(gutindex==1){
return true;
} else {
return hälfteOknlognPart(werte, gutindex);
}
}

static boolean hälfteOknn(int[] data, int l){
for(int i=0;i<l;i++){
// if contains
int k = 0;
for(int j=0;j<l;j++){
if(data[i] == data[j]){
k++;
}
}
if(k > l/2){
return true;
}
}
return false;
}

}

239043067s ago, by Antonio

and this task wasn't even evaluated. I hate this professor a little for that.