[アルゴリズム]バイナリ検索

6701 ワード
Java Divide and conquer アルゴリズム#アルゴリズム# テキストリンク

バイナリサーチ


バイナリ探索とは?


  • バイナリ検索は、昇順でソートされたリスト内で特定の値を検索するアルゴリズムである.
  • でソートされたリストでは、中間値に基づいて、検索する値が中間値より小さい場合は左側を繰り返し、右側より大きい場合は特定の値を検索します.
  • 提供およびConquer技術を使用します.
  • Divide:中間値を基準として、中間値より小さいリストと、中間値より大きいリストに分けられます.
  • Conquer:
  • の中間値==は、検索値、対応する値、またはインデックスを返します.
  • 中間値>ルックアップ値、中間値より小さいサブリストで
    • の数値を検索する.
  • 中間値<ルックアップ値、中間値より大きいサブリストで検索するデジタルナビゲーション
  • シーケンスの検索に比べて、一般的な検索速度は速い.
  • 上の写真を見ると、リストで37を検索するとSequenceは11回検索しており、検索値に比べてBinryの場合は3回検索で値を検索している.
  • ですが、必ずしもバイナリが速い場所ではありません.たとえば、上記の例のリストで1という数値をナビゲートすると、1回のナビゲーションバイナリ検索で4回のナビゲーションが必要になります.

    • Java実装コード

    public static int binarySearch(List<Integer> arr, int search) {
		// 데이터가 1개이고 그 데이터가 찾는 데이터면 True
		if (arr.size() == 1 && arr.get(0) == search)
			return 0;
		// 데이터가 1개인데 그 데이터가 찾는 데이터가 아니면 false
		if (arr.size() == 1 && arr.get(0) != search)
			return -1;
		// 데이터 자체가 없는 경우
		if (arr.size() == 0)
			return -1;
		
		int middle = arr.size()/2;
		if (arr.get(middle) == search)
			return middle;
		else {
			if (arr.get(middle) < search)
				return binarySearch(arr.subList(0, middle), search);
			else
				return binarySearch(arr.subList(middle, arr.size()), search);

		}
	}

    🔗 Reference

  • Fast Campas-JavaとSpring Web開発のプライマリ・ハイパー・パケットのオンライン化を一度に完了します。
  • https://blog.penjee.com/binary-vs-linear-search-animated-gifs/
  • https://velog.io/@delmasong/Algorithm-Binary-Search
    • Reactはクリックドラッグ機能onDragを実現
    3 Dステージ実装