Go Academy · レッスン

ソート済みデータの検索

Q: 「ソート済みデータの検索」レッスンは無料ですか？

はい。「ソート済みデータの検索」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Go Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Go Academyコースには全4レッスンが含まれています。

Q: 「ソート済みデータの検索」で何を学びますか？

二分探索を行います ブラウザで直接実行するハンズオンコードでGo Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Q: Go Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのGo Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。

Q: 「ソート済みデータの検索」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

Q: このGo Academyレッスンでコードを書いて実行できますか？

はい。すべてのGo Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

二分探索を行います

「ソート済みデータの検索」はCoddyKit上の無料Go Academyレッスンです。これはレッスン3/4です。下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。これはGo Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Go Academyコースには全4レッスンが含まれています。

ソート済みデータを検索する理由

スライスをソートしておけば、すべての要素を調べる代わりに二分探索を使って、要素をはるかに高速に見つけられます。

Go の sort パッケージには、対数時間で実行される検索ヘルパーが用意されています。

線形探索と二分探索

線形探索は各要素を1つずつ確認します（O(n)）。二分探索は各ステップで探索範囲を半分にします（O(log n)）。ただし、データがあらかじめソート済みである必要があります。

sort.SearchInts

sort.SearchInts は、値が存在するインデックス、またはスライスのソート順を保つために値を挿入すべきインデックスを見つけます。スライスはあらかじめ昇順にソートされていなければなりません。

package main

import (
	"fmt"
	"sort"
)

func main() {
	nums := []int{1, 3, 5, 7, 9}
	i := sort.SearchInts(nums, 5)
	fmt.Println("index:", i)
}

一致を確認する

SearchInts は、値が存在しない場合でもインデックス（挿入位置）を返します。必ず i < len(s) && s[i] == target を確認してください。

package main

import (
	"fmt"
	"sort"
)

func main() {
	nums := []int{1, 3, 5, 7}
	target := 4
	i := sort.SearchInts(nums, target)
	found := i < len(nums) && nums[i] == target
	fmt.Println("index:", i, "found:", found)
}

挿入位置

値が見つからない場合、返されるインデックスは、ソート順を保つためにその値を挿入すべき位置そのものです。ここでは4をインデックス2に挿入します。

package main

import (
	"fmt"
	"sort"
)

func main() {
	nums := []int{1, 3, 5, 7}
	i := sort.SearchInts(nums, 4)
	fmt.Println("insert 4 at index:", i)
}

SearchStrings

sort.SearchStrings は、ソート済みの文字列スライスに対して同じ処理を行います。

package main

import (
	"fmt"
	"sort"
)

func main() {
	words := []string{"apple", "cherry", "mango"}
	i := sort.SearchStrings(words, "cherry")
	fmt.Println("index:", i)
}

汎用的な sort.Search

sort.Search は柔軟な中核機能です。長さと、false の後に true になる関数 f を渡すと、f が true になる最小のインデックスを返します。

package main

import (
	"fmt"
	"sort"
)

func main() {
	nums := []int{2, 4, 6, 8, 10}
	i := sort.Search(len(nums), func(i int) bool {
		return nums[i] >= 6
	})
	fmt.Println("first >= 6 at index:", i)
}

しきい値を超える最初の要素を見つける

sort.Search は条件が true に変わる境界を見つけるため、しきい値より大きい最初の値を探すような処理に適しています。

package main

import (
	"fmt"
	"sort"
)

func main() {
	scores := []int{10, 20, 30, 40}
	i := sort.Search(len(scores), func(i int) bool {
		return scores[i] > 25
	})
	fmt.Println("first > 25:", scores[i])
}

最初にソートが必要

二分探索は順序が保たれていることを前提とします。スライスがソートされていなければ、結果に意味はありません。検索する前に必ずソートしてください。

package main

import (
	"fmt"
	"sort"
)

func main() {
	nums := []int{9, 1, 5, 3}
	sort.Ints(nums)
	i := sort.SearchInts(nums, 5)
	fmt.Println(nums, "-> index of 5:", i)
}

パフォーマンスの向上

要素が100万個あるスライスでは、線形探索は最大100万個を確認する可能性がありますが、二分探索では約20個を確認するだけです。一度ソートするコストは、何度も検索すれば元が取れます。

検索ヘルパーの選び方

まとめ：

sort.SearchInts / SearchStrings / SearchFloat64s - 型付きスライス
sort.Search - インデックスでアクセスできる任意のデータに対する独自条件

確認問題

4を含まないソート済みスライスに対して sort.SearchInts(s, 4) を呼び出すと、何が返されますか。

まとめ

二分探索でソート済みデータを検索する方法を学びました。

最初にデータをソートする必要があります
ヘルパーはインデックスまたは挿入位置を返します
等価性のチェックで一致を確認します
sort.Search では独自の条件を扱えます

よくある質問