二分探索 ジェネリクス

Question

Giga　　　キー入力
Giga は,配列の [0] にありました.
a[0] = name:Giga, vac:no
ペット名の探索をしたいです。上記の実行結果を得たいのですがジェネリクスのindexOfメソッドの作成を教えていただけるでしょうか

ジェネリクス
package exer3.search;

import java.util.List;
import java.util.Comparator;

public class BinarySearch<T> {
    private List<T> data;
    private Comparator<T> comparator;

    public BinarySearch(List<T> a, Comparator<T> c){
        data = a;
        comparator = c;
    }
//以下が分かりません
    public int indexOf(T query){
        int s = 0;
        int e = data.size() - 1;
        int c = comparator.compare(query,data);

        while(s <= e){


        }
    return -1;
    }   
}

Comments

[episteme]

二分検索するんですよね、なら要素をソートして構わんのですよね?
indexOf() はソートされた列でのインデックスを返して構わんのですよね?

[frere]

そうですね。

[frere]

メインクラスで名前は昇順に並べています。

[episteme]

ソート済のList<T>が与えられることを前提にした、"ほとんどコタエ"なヒントを置きました。

Answer 1

ひんと:

import java.util.List;
import java.util.Comparator;

public class BinarySearch {

    // java.util.Arrays.binarySearch とコンパチな二分探索
    // a は c に基づいてソートされていること。
    static <T> int binarySearch(List<T> a, T key, Comparator<T> c) {
        int first = 0;
        int count = a.size();

        while ( count > 0 ) {
            int count2 = count / 2;
            int mid = first + count2;
            if ( c.compare(a.get(mid),key) < 0 ) { // midより後半にあるハズ...
                first = mid + 1;
                count -= count2 + 1;
            } else if ( c.compare(a.get(mid),key) > 0 ) { // midより前半にあるハズ...
                count = count2;
            } else {
                return mid;
            }
        }
        return -first - 1;
    }

    // おためし
    public static void main(String[] args) {

        List<String> data = new java.util.ArrayList<String>();
        data.add("grape"); data.add("peach");
        data.add("banana"); data.add("cherry"); 
        data.sort((x, y)->{return x.compareTo(y);});
        for ( String item : data ) {
          System.out.printf("%s ", item);
        }
        System.out.println("\n----");

        String[] targets = new String[] { "apple", "grape", "melon", "strawberry" };

        for ( String target : targets ) {
            int result = binarySearch(data, target, (x, y)->{return x.compareTo(y);});
            if ( result >= 0 ) {
                System.out.printf("%s found at %d\n", target, result);
            } else {
                System.out.printf("%s NOT found. insertion point : %d\n", target, -result-1);
            }
        }

    }
}