001    package de.hska.info1.suchen;
002    
003    /**
004     * Schnelles Suchen nach einer Zahl in einem sortierten Feld.
005     * 
006     * @author Christian Pape
007     */
008    public class BinaerSuche implements Suchen {
009    
010        /**
011         * Sucht mit einem binären Unterteilungsverfahren rekursiv in der
012         * zahlenFolge nach einer zahl. Der Zeit- und Speicheraufwand dieser
013         * Implementierung ist O(log n) im schlimmsten Fall und O(1) im besten.
014         */
015        private boolean binaerSuchen(int[] zahlenFolge, int zahl, int links,
016                int rechts) {
017            if (rechts < links) {
018                return false;
019            } else {
020                int mitte = (links + rechts) / 2;
021                if (zahlenFolge[mitte] == zahl) {
022                    return true;
023                } else if (zahlenFolge[mitte] > zahl) {
024                    return binaerSuchen(zahlenFolge, zahl, links, mitte - 1);
025                } else {
026                    return binaerSuchen(zahlenFolge, zahl, mitte + 1, rechts);
027                }
028            }
029        }
030    
031            public boolean istEnthalten(int[] zahlen, int z) {
032                    return binaerSuchen(zahlen, z, 0, zahlen.length-1);
033            }
034    }