[アルゴリズム]バイナリナビゲーション

定義＃テイギ＃

バイナリルックアップアルゴリズムは、昇順に並べられたリストで特定の値の位置を検索するアルゴリズムです.初期中間値をランダムに選択し、その値と取得した値の大きさを比較する方法を採用します.最初に選択した中心値が検索値より大きい場合、この値は新しい最安値で、小さい場合は新しい最安値です.

ぎじふごう

// 재귀
이진탐색(arr, target, low, high) {
    if high <= low { // 관계 역전 -> 값 존재 X
        return -1
    }
    mid = (low + high) / 2 // 중간 값 선언
    // 배열에 대해 이진탐색 실행
    if arr[mid] > target { 
        return 이진탐색(arr, target, low, mid - 1)
    } else if arr[mid] < target {
        return 이진탐색(arr, target, mid + 1, high)
    } else {
        return mid;
    }
}

이진탐색(arr, target) {
    low, high = 0, arr.length - 1;
    while (low <= high) {
        mid = (low + high) / 2;
        if arr[mid] > value {
            high = mid - 1
        } else if arr[mid] < value {
            low = mid + 1
        } else {
            return mid
        }
    }
    return -1
}

の中間値がtargetより大きい場合、左側のアレイにtargetが存在する可能性があります.highはmid-1に変換し、バイナリナビゲーション

を実行する.

の中間値がtargetより小さい場合、対半の配列では右側の配列にtargetが存在する可能性があります.lowはmid+1となり、バイナリナビゲーション

を再実行する