バイナリサーチ
6326 ワード
🤔コンセプト
バイナリ検索アルゴリズムは、昇順に並べられたリスト内で特定の値の位置を検索するアルゴリズムです.
利点:検索を繰り返すたびに、ターゲット値を検索する確率がターゲット値の2倍になるため、速度が速くなります.
欠点:検索原理(中間値を検索する必要がある)でソートされたリストにのみ適用されます.
📌 さぎょうモード
📌 操作アルゴリズムの説明
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.");
}バイナリナビゲーションの例
ソース
Reference
この問題について(バイナリサーチ), 我々は、より多くの情報をここで見つけました https://velog.io/@eunoia/이진-탐색-Binary-Searchテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol