# 機能設計書 28-検索・探索

## 概要

本ドキュメントは、Julia Base ライブラリが提供する検索・探索機能の設計について記述する。配列やコレクション内の要素を条件に基づいて検索し、インデックスや要素そのものを返す関数群を提供する。

### 本機能の処理概要

検索・探索機能は、`findfirst` / `findlast` / `findall` / `findnext` / `findprev` による条件一致検索と、`searchsorted` / `searchsortedfirst` / `searchsortedlast` / `insorted` によるソート済み配列の二分探索を提供する。これらは配列だけでなく、文字列やイテレータに対しても適用可能である。

**業務上の目的・背景**：データ内から特定の条件を満たす要素やその位置を見つけることは、データ処理・アルゴリズム実装の基本操作である。線形探索による任意条件検索と、ソート済みデータに対する O(log n) の二分探索の両方を提供し、用途に応じた効率的な検索を可能にする。

**機能の利用シーン**：配列内の特定値の位置検索、条件を満たす全要素のインデックス取得、ソート済みデータへの挿入位置決定、文字列内の文字・部分文字列検索、フィルタリングのためのインデックス生成で利用される。

**主要な処理内容**：
1. `findfirst(pred, A)` - 最初の条件一致インデックスを返す
2. `findlast(pred, A)` - 最後の条件一致インデックスを返す
3. `findall(pred, A)` - 全条件一致インデックスの配列を返す
4. `findnext(pred, A, i)` - i以降の次の条件一致インデックスを返す
5. `findprev(pred, A, i)` - i以前の前の条件一致インデックスを返す
6. `searchsorted(A, x)` - ソート済み配列でのxの挿入範囲を返す
7. `searchsortedfirst(A, x)` - ソート済み配列でのxの最初の挿入位置
8. `searchsortedlast(A, x)` - ソート済み配列でのxの最後の挿入位置
9. `insorted(x, A)` - ソート済み配列にxが含まれるかの判定
10. `findmax` / `findmin` - 最大値/最小値とそのインデックスの同時取得

**関連システム・外部連携**：なし。Base モジュール内で完結する。

**権限による制御**：なし。すべてのユーザーが利用可能である。

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| - | - | - | 画面関連なし（ライブラリ関数） |

## 機能種別

計算処理（検索・探索アルゴリズム）

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| pred | Function / value | Yes | 検索条件（述語関数またはisequalで比較する値） | 呼び出し可能 / 任意の値 |
| A | AbstractArray / String | Yes | 検索対象のコレクション | indexable であること |
| i | Integer | No | 検索開始位置 | 有効なインデックス範囲内 |
| x | Any | Yes（searchsorted系） | 二分探索の対象値 | 比較可能であること |
| lt | Function | No | 比較関数（デフォルト isless） | 全順序を定義する関数 |
| by | Function | No | 変換関数（デフォルト identity） | 呼び出し可能 |
| rev | Bool | No | 逆順ソートかどうか | true / false |

### 入力データソース

Julia プログラム内の配列、文字列、その他コレクション。

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| index | Int / CartesianIndex / nothing | 見つかった要素のインデックス（見つからない場合 nothing） |
| indices | Vector{Int} / BitVector | findall の結果（全一致インデックス） |
| range | UnitRange{Int} | searchsorted の結果（挿入範囲） |
| (value, index) | Tuple | findmax/findmin の結果 |

### 出力先

呼び出し元への戻り値。

## 処理フロー

### 処理シーケンス

```
1. findfirst(pred, A) が呼ばれる
   └─ findnext(pred, A, firstindex(A)) に委譲
2. findnext(pred, A, i)
   └─ i から lastindex(A) まで走査
   └─ pred(A[j]) が true なら j を返す
   └─ 見つからなければ nothing を返す
3. findall(pred, A)
   └─ 結果配列を作成
   └─ 全要素を走査、pred が true のインデックスを push!
4. searchsortedfirst(A, x)
   └─ 二分探索: lo = firstindex(A)-1, hi = lastindex(A)+1
   └─ while lo < hi - 1: mid = (lo+hi)>>>1
   └─ lt(A[mid], x) ? lo = mid : hi = mid
   └─ hi を返す
5. insorted(x, A)
   └─ searchsorted(A, x) で範囲を取得
   └─ 範囲が空でなければ true
```

### フローチャート

```mermaid
flowchart TD
    A[検索・探索] --> B{関数種別}
    B -->|findfirst/findnext| C[線形走査: i → lastindex]
    B -->|findlast/findprev| D[線形走査: i → firstindex]
    B -->|findall| E[全走査 + push!]
    B -->|searchsorted系| F[二分探索]
    B -->|findmax/findmin| G[全走査 + 比較]
    C --> H{pred true?}
    H -->|Yes| I[インデックス返却]
    H -->|No| J[次の要素へ]
    J --> H
    F --> K{lo < hi - 1?}
    K -->|Yes| L[mid = lo+hi >>> 1]
    L --> M{lt A_mid x?}
    M -->|Yes| N[lo = mid]
    M -->|No| O[hi = mid]
    N --> K
    O --> K
    K -->|No| P[hi を返却]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-01 | nothing 返却 | findfirst/findnext/findprev は見つからない場合 nothing を返す | 要素が見つからない場合 |
| BR-02 | 空範囲 | searchsorted は要素が見つからない場合空の UnitRange を返す | 要素不存在時 |
| BR-03 | ソート前提 | searchsorted 系関数はソート済み配列を前提とする | 常時 |
| BR-04 | isequal比較 | findall(x, A) の値検索は isequal を使用 | 値で検索する場合 |
| BR-05 | Bool配列最適化 | findall(A::AbstractArray{Bool}) は true のインデックスを返す | Bool配列の場合 |

### 計算ロジック

- 線形探索: O(n) - findfirst / findlast / findall / findnext / findprev
- 二分探索: O(log n) - searchsorted / searchsortedfirst / searchsortedlast / insorted
- `searchsortedfirst`: `lo < hi - 1` の間、`mid = (lo + hi) >>> 1` で中間点を計算

## データベース操作仕様

### 操作別データベース影響一覧

該当なし（インメモリ計算のみ）。

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| - | BoundsError | findnext/findprev に範囲外のインデックスを指定 | 有効範囲内のインデックスを使用 |
| - | MethodError | 比較不可能な要素型で searchsorted | 比較可能な型を使用するか lt を指定 |

### リトライ仕様

リトライは不要。

## トランザクション仕様

該当なし。

## パフォーマンス要件

- 線形探索: O(n) 時間
- 二分探索: O(log n) 時間
- findall(::AbstractArray{Bool}): ビット配列の場合に最適化された実装

## セキュリティ考慮事項

特になし。

## 備考

- `findfirst` / `findnext` は文字列に対しても使用可能（文字・部分文字列・正規表現の検索）
- `findall(pattern, string)` は文字列検索として機能（No.30 文字列検索・置換 と関連）
- `searchsorted` は `sort.jl` で定義されており、ソート機能（No.20）と密接に関連

---

## コードリーディングガイド

本機能を理解するために参照すべきファイルと、推奨する読み解き順序を以下に示す。

### 推奨読解順序

#### Step 1: データ構造を理解する

検索・探索は特別なデータ構造を定義しないが、Fix2 パターンと述語関数のディスパッチを理解する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | array.jl | `base/array.jl` | findfirst, findnext, findall の配列版実装 |

**読解のコツ**: Julia の find 系関数は多重ディスパッチにより、述語関数版（`findfirst(pred, A)`）と値検索版（`findfirst(isequal(x), A)`）を同一インタフェースで提供する。`Fix2` パターンにより `isequal(x)` が部分適用として最適化される。

#### Step 2: 線形検索を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | array.jl | `base/array.jl` | findfirst, findnext, findlast, findprev の実装 |

**主要処理フロー**:
- findfirst は findnext に firstindex で委譲
- findnext は i から lastindex まで走査して pred チェック
- findall は結果配列に push! しながら全走査

#### Step 3: 二分探索を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | sort.jl | `base/sort.jl` | searchsorted, searchsortedfirst, searchsortedlast の実装 |

**主要処理フロー**:
- searchsortedfirst: `lo < hi - 1` ループで `mid = (lo+hi)>>>1` により中間点計算
- insorted: searchsorted の結果範囲が空でなければ true

### プログラム呼び出し階層図

```
findfirst(pred, A) / findall(pred, A) / searchsortedfirst(A, x)
    |
    +-- findfirst(pred, A)
    |       +-- findnext(pred, A, firstindex(A))
    |               +-- 線形走査: pred(A[i]) チェック
    |
    +-- findall(pred, A)
    |       +-- [Bool配列] 最適化パス
    |       +-- [その他] 全走査 + push!
    |
    +-- searchsortedfirst(A, x; lt, by, rev)
    |       +-- 二分探索ループ
    |       +-- lt(by(A[mid]), by(x)) で比較
    |
    +-- insorted(x, A)
            +-- searchsorted(A, x)
            +-- !isempty(range)
```

### データフロー図

```
[入力]                      [処理]                           [出力]

pred, A (Array)      ---->  findfirst(pred, A)
                            +-- 線形走査                     ---->  Int / nothing

pred, A (Array)      ---->  findall(pred, A)
                            +-- 全走査 + push!               ---->  Vector{Int}

x, A (sorted Array)  ---->  searchsortedfirst(A, x)
                            +-- 二分探索                     ---->  Int (挿入位置)

x, A (sorted Array)  ---->  insorted(x, A)
                            +-- searchsorted → isempty        ---->  Bool
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| array.jl | `base/array.jl` | ソース | findfirst, findnext, findall 等の配列版検索関数 |
| sort.jl | `base/sort.jl` | ソース | searchsorted, searchsortedfirst, searchsortedlast, insorted 等の二分探索 |
| strings/search.jl | `base/strings/search.jl` | ソース | 文字列版の findnext, findprev（文字・パターン検索） |
| abstractarray.jl | `base/abstractarray.jl` | ソース | 汎用配列の find 系関数のフォールバック実装 |
