バイナリサーチ

🤔コンセプト

バイナリ検索アルゴリズムは、昇順に並べられたリスト内で特定の値の位置を検索するアルゴリズムです.
利点:検索を繰り返すたびに、ターゲット値を検索する確率がターゲット値の2倍になるため、速度が速くなります.
欠点:検索原理(中間値を検索する必要がある)でソートされたリストにのみ適用されます.

📌 さぎょうモード

アレイの中間値を任意の値

として選択する.

中央値と検索する値のサイズの比較

中央値=検索値:検索値、検索終了

中央値>ルックアップ値:中央値ベースのアレイの左側にある

に移動します.

中央値<ルックアップ値:中央値に基づくアレイの右側にある

に移動する.

の値を検索するか、間隔が0になるまで

を繰り返します.

リストで検索する値と同じ要素が見つかった場合(検索に成功)、

検索範囲がない場合(検索に失敗)

📌 操作アルゴリズムの説明

0.前置条件

배열 : arr[1,2,3,4,5,6,7]
찾는 값 : 5 

1.配列の中間値を任意の値として選択

key(찾는 값) : 5
mid(중앙 값) : 4
검색 범위 : 1, 2, 3, 4, 5, 6, 7

2.中心値と検索する値のサイズを比較する
2-1. 중앙값(4) < 찾는 값(5):中央値アレイの右側の領域に移動
(値を検索するか、間隔が0になるまで繰り返します)

key(찾는 값) : 5
mid(중앙 값) : 6
검색 범위 : 4, 5, 6, 7 

2-중앙값(6) > 찾는 값(5):中央値アレイの左側の領域に移動
(値を検索するか、間隔が0になるまで繰り返します)

key(찾는 값) : 5
mid(중앙 값) : 5
검색 범위 : 4, 5, 6 

2-3中央値=検索値:検索値、検索終了
3.間隔が0になるまで値の検索を繰り返す
💡 TIP. ちゅうしんちけいさんしき

int mid = (low + high) / 2


//만약 배열의 크기가 커지게 된다면 
//low + high를 했을 때 int 범위를 벗어날 수 있기에 이렇게 사용하는편이 좋음
int mid = low + (hight-low) / 2

表時間の複雑さとbigoタグ

Θ(log n)

💻 JAVAによるバイナリナビゲーションアルゴリズムの実装

public int binarySearch(int[] arr, int target) {
    int start = 0;
    int end = arr.length - 1;
    int mid = 0;

    while (start <= end) {
        mid = (start + end) / 2;
        if (target == arr[mid]) {
            return mid;
        }else if (arr[mid] < target) {
            start = mid + 1;
        }else if (target < arr[mid]) {
            end = mid - 1;
        }
    }
    throw new NoSuchElementException("can't find target.");
}

バイナリナビゲーションの例

ソース

https://ko.wikipedia.org/wiki/バイナリサーチアルゴリズム

https://yoongrammer.tistory.com/75