https://annajeong.github.io/algorithm/parametric/

https://movefast.tistory.com/311

https://www.youtube.com/watch?v=F6lKjRDlOpk

https://hee96-story.tistory.com/80

バイナリナビゲーション

整然とした配列でしか使用できません

アレイ内部のデータを並べ替えて使用するアルゴリズム.

探索範囲を半分に絞る特徴がある.

3変数=始点、終点、中間点

検索するデータと中間位置にあるデータを繰り返し比較し、欲しいデータを探す.

バイナリナビゲーションプロセス
1.手順
0246810141618始点[0]中点[4]終点[9]

始点と終点を確認して中点を確定する.

中間点がミスであれば小数点以下を放棄する.

中点[4]のデータを検索するデータ4と比較する.

中間点のデータがより大きく、(8)確認することなく[4]以前の[3]に端点を移動する.

2.手順
0246810141618始点[0]中点[1]終点[3]

始点[0]と終点[3]の中点を求める[1].

中間点にあるデータ2は検索するデータ4より小さいので、中間点以下のデータをチェックする必要はない

始点を[2]に変更

3.手順
0246810141618始点[2]、中点[2]終点[3]

始点[2]と終点[2]の中点[2]を求める.

中間点にあるデータは検索するデータと同じであるため、現在探索を終了する.

全てのデータは10個であるが、バイナリ検索により合計3回の検索で要素を見つけることができる.

一度確認するごとに確認した要素の数が半分に減る.

時間複雑度:O(logn)

再帰関数で実現されるバイナリ探索

def binary_search(array, target, start, end):
  if start > end:
    return None

  mid = (start + end) // 2

  if array[mid] == target:
    return mid
  elif array[mid] > target:
    return binary_search(array, target, start, mid - 1)
  elif array[mid] < target:
    return binary_search(array, target, mid + 1, end)


n, target = map(int, input().split())
array = list(map(int, input().split()))

result = binary_search(array, target, 0, n - 1)
if result is None:
  print("원소가 존재하지 않습니다.")
else:
  print(result + 1)

重複文によるバイナリ・ナビゲーション

def binary_search(array, target, start, end):
  while start <= end:
    mid = (start + end) // 2

    if array[mid] == target:
      return mid
    elif array[mid] > target:
      end = mid - 1
    else:
      start = mid + 1
  return None


n, target = map(int, input().split())
array = list(map(int, input().split()))

result = binary_search(array, target, 0, n - 1)
if result is None:
  print("원소가 존재하지 않습니다.")
else:
  print(result + 1)

Lower Bound & Upper Bound

Lower boundは、データの最初の値が値以上の位置を返します.

Python分割モジュールの分割left

low bound関数

def lower_bound(data, target):
    lo = 0
    hi = len(data)
    while lo < hi:
        mid = (lo + hi) // 2
        if target <= data[mid]:
            hi = mid
        else:
            lo = mid + 1
    return lo

対分left関数

def bisect_left(a, x, lo=0, hi=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        # Use __lt__ to match the logic in list.sort() and in heapq
        if a[mid] < x: lo = mid+1
        else: hi = mid
    return lo

Upper Boundは、ある値よりも大きい最初の位置を返します.

Pythonスコアモジュールのスコアright

upper bound関数

def upper_bound(data, target):
    lo = 0
    hi = len(data)

    while lo < hi:
        mid = (lo + hi) // 2
        if target >= data[mid]:
            lo = mid + 1
        else:
            hi = mid
    return lo
    
    
arr=[50, 80, 81, 150, 150, 150, 150, 210, 260]
target=150
lower_bound = 3
upper_bound = 7

たいぶんrightかんすう

def bisect_right(a, x, lo=0, hi=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        # Use __lt__ to match the logic in list.sort() and in heapq
        if x < a[mid]: hi = mid
        else: lo = mid+1
    return lo

参照パラメータ

最適化問題を意思決定問題に変換する技術

最適化問題👉 どのアルゴリズムのベストソリューションを見つけるか

意思決定問題👉 回答が決まったので回答(マットレス問題)

パラメータナビゲーションの問題はいつ使用できますか?

けっていもんだい

ある時点で条件が満たされているが、その時点以降条件が満たされていない場合は最値が検索される(Upper Bound)

ある時点までは条件を満たしていませんが、その時点以降で条件を満たした場合に最小値を検索します.

パラメータナビゲーションの操作手順

問題で最終的に探している最高額/最低価格をパラメータとします.

決定関数を定義して実現した場合、結果の並びが連続しているかを確認する.

最大値であれば、結晶関数を探す結果は[f,f,...,t,t]からf->tの部分に変わる.

最安値であれば、決定関数を探す結果は[t,t,...,f,f]からt->fの部分に変わる.

バイナリプローブとの違い

バイナリ探索👉 targetに一致する値が見つかった場合は、関数を終了して位置に戻る

閲覧パラメータ👉 targetに一致する値が見つかっても、関数を終了するのではなく、ナビゲーションする配列がなくなるまでナビゲーションを続行します.

パラメータ区間の定義

# 1
def binary_search(arr,lo,hi,value):
    while lo + 1 < hi:
        mid = (lo + hi) // 2
        if arr[mid] <= value:
          lo = mid
        else:
          hi = mid
    return arr[lo]

条件lo + 1 < hi👉 複文内、arr[lo] < arr[hi]常成立

loとhiの各差1(hi-lo == 1)
👉 mid <=hiまたはlo <= midarr[lo] < arr[hi]成り立たないかも

loとhiの差が1以上(hi-lo > 1)
👉 arr[lo] < arr[hi]食べ物は変わらない.

評価条件に基づいて、loまたはhiが正解です.

条件arr[mid] <= value👉 arr[lo] == value

条件arr[mid] < value👉 arr[hi] == value

lo、hi区間の定義👉 lo = 구간의 최솟값 -1 & hi = 구간의 최댓값

・lo = 구간의 최솟값で定義し、hiは区間の最高値にはならない.
( lo + 1 < hi )

インプリメンテーション決定関数

# 2
def fn(param):
    pass
    
def binary_search(arr,lo,hi,value):
    while lo + 1 < hi:
        mid = (lo + hi) // 2
        if fn(mid):
          lo = mid # 참이면 오른쪽 구간을 탐색
        else:
          hi = mid # 거짓이면 왼쪽 구간을 탐색
    return arr[lo]

fn(param) := paramある条件を満たし、trueまたはfalseを返すことを表す.

param 👉 一般的に、問題で最終的に要求される最も高い/最も高い値は、探しているパラメータです.

paramの範囲は連続しているはずです.

[lo, hi]間の値

fn(param)の範囲も連続する.

[false, false, ..., false, true, ..., true, true]または[true, true, ..., true, false, ..., false, false]

中間false -> true 또는 true -> false 로 바뀌는 부분1回のみ存在する.

複数あれば3点探索など他の方法で解決する.

어떤 조건 👉 param以上/以下の場合、MグループまたはMグループに分割できますか?