バイナリナビゲーション

10440 ワード
テキストリンク
英語の辞書でgooseを探したい時辞書はabcdです.順番に並んでいることを知っているからです.
必ずしもa単語集の場所で探すのではなく、g単語集の場所から探す.
検索する範囲で、中間値が検索する値と一致していることを確認します.
一致する場合は、中間値の位置を返します.
中間値が検索する値より大きい場合は、最大値を中間値位置-1に再調整します.
中間値が検索する値より小さい場合は、最小値を中間値位置+1に再調整します.
中間値が見つからないまで繰り返す
どんなに範囲が広くてもO(logn)で終わります.探索すればするほど,探索の範囲は小さくなる.
binary search関数は、ソートされた配列とアイテムを受け入れます.アイテムが並べ替えられている場合は、並べ替えられているアイテムの位置を返します.
import math

array = list(range(1, 101))

item = 75

def binary_search(item: int) -> int or None:

    min_index = 0
    max_index = len(array)-1

    while min_index <= max_index:

        middle_index = math.floor((min_index+max_index) / 2)

        if(array[middle_index] == item):
            return middle_index

        if(array[middle_index] > item):
            max_index = middle_index-1

        if(array[middle_index] < item):
            min_index = middle_index+1

    return None

print(binary_search(item))
import java.lang.Math;

public class BinarySearch {

    private static int binarySearch(int item, int[] array) {

        int minIndex = 0;

        int maxIndex = array.length - 1;

        while (minIndex <= maxIndex) {

            int middleIndex = (int) Math.floor((minIndex + maxIndex) / 2);

            if (array[middleIndex] == item) {
                return middleIndex;
            }

            if (array[middleIndex] > item) {
                maxIndex = middleIndex - 1;
            }

            if (array[middleIndex] < item) {
                minIndex = middleIndex + 1;
            }

        }
        return -1;
    }

    public static void main(String[] args) {

        int[] array = new int[100];

        for (int i = 0; i < array.length; i++) {
            array[i] = i + 1;
        }

        int item = 65;
        System.out.println(binarySearch(item, array));

    }
}
[TIL]21.05.03
Liman Mes ' de Ekentienti Geli Triilmesi ( Tab ' l Ship Yap Cement )