二分探索法

2分探索を書く機会があったので、メモとして記述しておきます。

2分探索とは

データを探索するときに使うアルゴリズム。 ソート済みのデータの範囲を絞りながら探索を続けることできる。 高速に探索を行う手法。

２分探索は全体の配列から半分ずつ範囲を絞りながら、検索するアルゴリズムなだけに
はやい。

Sample.java

int algorithm(int[] data, int target) {
    int retrieve = -1;
    int left = 0;
    int right = data.length - 1;
   
    while(left < right){
        int mid = (left + right)/ 2;
        if(data[mid] == target){
            return mid + 1;
        }else if(target < data[mid]){
            return right = mid;
        }else {
            return left = mid + 1;
        }
    }
    return retrieve;
}

まとめ

ソート済みであるなら、２分探索の方が良いですね