1.2 二分探索

一覧へ戻る

概要

　1.1で示した線形探索は言ってしまえばマシン っぽいアルゴリズムである．
　私たちは辞書を使うとき，一発で探したい単語の書かれているページを開けることは めったにないが，もし違うページを開いてしまっても，探したい単語がそのページの 前にあるのか後ろにあるのかを理解することができる．
　二分探索はその要領で探索すべきデータの範囲を少なくしていく(機械的に二分割 していく)ことで実装する．ただし，探索対象となる表はあらかじめ昇順に 並び替えられているとする．

実装例

　二分探索は以下のコードのように実装することができる． 


while(low <= high){
    int middle = (low + high)/2;
    int status = strcmp(key, data[middle].getKey());
    if(key == 注目データ　なら){
        return mならdle;
    }else if(key < 注目データ　なら){
        high = middle -1;
    }else{
        low = middle + 1;
    }
}
        

import java.util.Arrays;

public class BinarySearch {
    static int[] table = { 4, 2, 11, 4, 3, 2, 35, 3535, 353535 };

    static int binarySearch(int key) {
        int low = 0;
        int high = table.length - 1;
        while (low <= high) {
            int middle = (low + high) / 2;
            if (table[middle] == key) {
                return middle;
            } else if (table[middle] < key) {
                low = middle + 1;
            } else {
                high = middle - 1;
            }
        }
        return -1;
    }

    static void printArray() {
        System.out.print("table = {");
        for (int i = 0; i < table.length; i++) {
            System.out.printf("%d", table[i]);
            if (i != table.length - 1) {
                System.out.printf(", ");
            }
        }
        System.out.println("}");
    }

    public static void main(String[] args) {
        Arrays.sort(table);
        int key = 3535;
        System.out.printf("key = %d\n",key);
        printArray();
        
        int index = binarySearch(key);
        if (index != -1) {
            System.out.printf("key == table[%d]", index);
        } else {
            System.out.println("could not find key(3535)");
        }
    }

}


        
$ java BinarySearch

table = {2, 2, 3, 4, 4, 11, 35, 3535, 353535}
key == table[7]

計算量

以上．(2025-11-16_00:28) 一覧へ戻る