記事の概要

文字列を二分探索する関数 sort.SearchStrings は、その返り値では、
探索対象の文字列が存在するか、存在しないかが判断できない。
その説明と対策コードを考え、書いた。

参考文献

https://golang.org/pkg/sort/#SearchStrings
https://golang.org/src/sort/search.go?s=3680:3724#L91

sort.SearchStrings の仕様

sort.SearchStrings は公式ドキュメントによると、
昇順にソートされた文字列スライスと文字列xを受け取り、スライスの中にxがあるか二分探索する。
文字列スライスの中にxが存在する場合, そのインデックスを返し、
文字列スライスの中にxが存在しない場合、そのスライスに、昇順を維持して、xを挿入するためのインデックスを返す。

func SearchStrings(a []string, x string) int
SearchStrings searches for x in a sorted slice of strings and returns the index 
as specified by Search. The return value is the index to insert x if x is not 
present (it could be len(a)). The slice must be sorted in ascending order.

何を問題としているか

返り値から探索対象の文字列が存在するか、存在しないかが判断できない。
例えば、以下のコードでコメントは出力結果を表しているが、以下の結果が一致してしまっている

a を探索した場合: スライスに a がなく、a の挿入位置 0 が返る
b を探索した場合: スライスに b があり、その位置の 0 が返る

var slice = []string{"b"}

fmt.Println(sort.SearchStrings(slice, "a")) // 0
fmt.Println(sort.SearchStrings(slice, "b")) // 0
fmt.Println(sort.SearchStrings(slice, "c")) // 1

どうするのか

返ったインデックスを元に、スライスにアクセスし、その文字列と探索文字列が等しいか調べる。
ただし、公式ドキュメントの言及(it could be len(a))や、上の例の c の探索のように、
範囲外のインデックスが返る場合があるので、その場合を避けて考える。以下がそのコードである.

	var target = "b"
	var slice = []string{"b", "d"}
	var idx = sort.SearchStrings(slice, target)

	// 存在するかを調べる
	if idx != len(slice) && slice[idx] == target {
		fmt.Println("Exists")
	}

	// 存在しないことを調べる
	if idx == len(slice) || slice[idx] != target {
		fmt.Println("None")
	}