2分探索

binary-search.png

高速に探索するための強力なツール!です

2分探索が有効な時

  • 既にソートされているデータから、ある値を探す

基本 完全一致したデータを見つけたら抜ける

1 3 5 11 12 13 17 22 25 28

public class Miffy {
    public static int data[]={1,3,5,11,12,13,17,22,25,28};//10
    public static int value=28;
    static void binary_search(int start,int end){
        int pos=(start+end)/2;
        System.out.println("start="+start+", end="+end+" data="+data[pos]);
        if(data[pos]!=value){
 
            if(data[pos]<value){
                System.out.println("後半");
                binary_search(pos,end);
            }else{
                System.out.println("前半");
                binary_search(start,pos);
            }
            }else{
                System.out.println("見つかりました!");
                }
 
    }
    public static void main(String[] args) {
            binary_search(0,data.length);
    }
 
}

ちょっと応用:もっとも近い値を返す

public class Miffy {
    public static int data[]={1,3,5,11,12,13,17,22,25,28};//10
    public static int value=10;
    public static boolean last_direction=false;
    public static int lower_limit=0;
    public static int upper_limit=data.length;
    static void binary_search(int start,int end){
        int pos=(start+end)/2;
        System.out.println("start="+start+", end="+end+" data="+data[pos]+" upper="+upper_limit+" lower="+lower_limit);
        if(upper_limit-lower_limit<=1){
            System.out.println("答えは"+lower_limit+"番目と"+upper_limit+"の間");
            return;
        }
        if(data[pos]==value){
            System.out.println("見つかりました!");
            return;
        }
            if(data[pos]<value){
                System.out.println("後半");
                lower_limit=pos;
                binary_search(pos,end);
            }else{
                System.out.println("前半");
                upper_limit=pos;
                binary_search(start,pos);
            }        
    }
    public static void main(String[] args) {
            binary_search(0,data.length);
    }
 
}

algorithm reverse-engineering

サポートサイト Wikidot.com algorithmreverse-engineering