---
title: 最初の要素を返す二分探索
tags: []
categories: ["Programming", "Algorithm", "BinarySearch"]
date: 2011-05-24T03:50:13Z
updated: 2011-05-24T03:50:13Z
---

`java.util.Collections#binarySearch`は指定されたオブジェクトと同等の要素が複数ある場合に、どれが検索されるかについての保証してくれない。

Suffix Array作った時とかは最初の要素を検索してほしい。↓のように実装すれば同等の要素が複数ある場合に最初の要素を取得できる。

    public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c) {
        int l = -1;
        int size = list.size();
        int u = size;

        while (l + 1 != u) {
            int m = (l + u) / 2;
            T v = list.get(m);

            if (c.compare(v, key) < 0) {
                l = m;
            } else {
                u = m;
            }
        }

        int p = u;
        if (p >= size || c.compare(list.get(p), key) != 0) {
            p = -1;
        }
        return p;
    }

ループの中で探している要素と一致しても終了せず、上方のポインタを下げるところがポイント。
こうするとこで、下方のポインタと上方のポインタが隣り合ったとき、
要素があるとしたら最初にみつかる位置が情報のポインタが差す位置になる。