Binary Search

Binary Search

バイナリを検索しますか?この探索?バイナリを探索しますか?コンセプトは...
Binary Search
バイナリ検索アルゴリズム(binary search algorithm)は、昇順に並べられたリスト内で特定の値の位置を検索するアルゴリズムである.初期の中間から任意の値として値を選択し、検索する値のサイズと比較します.最初に選択した中心値が検索値より大きい場合、この値は新しい最安値で、小さい場合は新しい最安値です.検索原理上の欠点はソートにしか使用できないリストであるが,検索を繰り返すたびにターゲット値を見つける確率が元の2倍になるため,速度が速い.
ありがとうございます!
長さNのソート配列で必要な値の位置を検索します.
時間複雑度O(logn)O(logn)O(logn)
検索するだけで多すぎるのを省くことができることを証明して、約長さNの配列を半分に分けて、それからkを除いて、N=2 KN=2^{k}N=2 kになりました...

インプリメンテーション

指定された配列で必要な値の位置を検索する機能には、次のものがあります.
Pythonは、内蔵ライブラリ対ライブラリとして簡単に使用できます.ポイントを開けろ

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

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

昇順で配列された配列aとターゲット値xが受信された場合、xを挿入すると、配列内で並べ替えを維持するためにインデックス値が返されます.
ライブラリ関数はCによって駆動されるので、より高速です.使えるなら使ってください.

では、なぜこの探索を学ぶのでしょうか。

これは,中央値調査後の区間再設定で効果的に解決できる問題が多いためである.
特に,パラメータ探索と分割征服問題においても同様の考え方を用いた.
分割征服については,midを基準として与えられた問題を分割し,より小さな区間を繰り返し分割して問題を解く.分割時は主に区間の中心値を利用する.(必ずしも中央値ではありません.)

def quick_sort(arr):
    def sort(low, high):
        if high <= low:
            return None

        mid = partition(low, high)
        sort(low, mid - 1)
        sort(mid, high)

    def partition(low, high):
        pivot = arr[(low + high) // 2]
        while low <= high:
            while arr[low] < pivot:
                low += 1
            while arr[high] > pivot:
                high -= 1
            if low <= high:
                arr[low], arr[high] = arr[high], arr[low]
                low, high = low + 1, high - 1

        return low

    return sort(0, len(arr) - 1)


def merge_sort(arr):
    def sort(low,high):
        if high-low <= 1:
            return arr[low:high]

        mid = (low+high)//2
        left_list = sort(low,mid)
        right_list = sort(mid,high)
        return merge(left_list,right_list)

    def merge(left,right):
        result = []
        i = 0
        j = 0
        while i < len(left) or j < len(right) :
            if i < len(left) and j < len(right):
                if left[i] <= right[j]:
                    result.append(left[i])
                    i += 1
                else:
                    result.append(right[j])
                    j += 1
            elif i < len(left):
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1
        return result
    return sort(0,len(arr))

分割征服の叡仁Quick SotとMergeSot
Parametric Searchは決定問題(これより良い答えはありますか?)最適化問題(最適化の答えは何ですか?)に変更できます.
与えられた条件では,可能な限り最小値を求めるか,最大値を求める問題では,答えの候補の最小値をlow bound,候補の最大値をuper boundとし,二分探索により条件を満たす境界を見つけることができる.

君が描いた絵は...
感じがわかるでしょ?^~^
例
BOJローカルエリアネットワークのクリップ
BOJ木を切る
(全部切れた)

だからいつ使えばいいですか?

最適化問題は必ずしも二分探索だけで解決できるとは限らない.
場合によっては、グリッドアルゴリズム、ダイナミックプログラミング、(後続)完全なナビゲーションがより良い場合があります.時には、問題を表す公式だけが構築され、そのまま解決されることもある.
個人的には関数のタイプはよくわかりませんが、xにとってf(x)を求めるのがそんなに難しくなければ、点火式がなければ、最適解が唯一の値であり、多変数であれば、最適解を基準にf(x)値を決定する場合(単調関数の場合)、二分探索が近づくと発光します.

この場合...xのf(x)値を求めることにより,二分探索により最適xを見つけることができる.

このようなf(x)や臨界条件を与えて、赤い線と出会った部分を見つければ、この探索は馬鹿になる...ううう
(適当な区間設定は悪くないですが、他の方法の方が役に立つかもしれません)
また,意外な問題も二分探索を用いて近づくことができる.

与えられた関数の極値を求める問題は,関数の概略を知れば微分により容易に求めることができるが,知らなければf(x)f(x+1)のときのTrueをTrueと見なし,二分探索によりxcx cxcを求めることができる.
この場合、二分法ではなく三分法で解くこともできる.
アルゴリズム解題では,二分探索の核心思想区間を二つに分け,f(mid)値に基づいて区間を選択し,区間を縮小する方法は熟知しているが,うまくいけばよいが,与えられた問題でf(x)の関数を実現し,二分探索が実行可能であるかどうかを検証することが重要である.
推奨事項
BOJ通常タワーサーバ
タイプは二分探索で書く必要のない問題
BOJの2つの数の和
同じタイプは二分探索であり,二重積分アルゴリズムはより解きやすい.
Programmers荊棘橋
こちらの探索で解けたのですが、グリディでも完全に解けます.
私はずっとこの探求の問題を書かないでアップロードしています.
Programmers運搬金銀
月度コードは第3四半期9月3日の問題に挑戦し、この探索は正しいが、f(x)を探すのは頭の痛い問題である.解けなかった
BOJヴァンパイア金相根伯爵
二分探索を用いて完全探索の擬動作数を減らす.
実装中によく発生する問題
この文章はよく整理されているので、直接リンクします。
left=mid+1かright=mid-1か、whilet