Java 古典アルゴリズム二分探索の原理と実装の図解

この記事では、java に関する関連知識を提供します。半検索方法は二分検索とも呼ばれます。名前が示すように、データを 2 つの半分に分割し、どちらの半分のキーを探しているかを決定します。 . を実行し、目的のキーが見つかるまで上記の手順を繰り返します。

推奨学習: 「java ビデオ チュートリアル 」

二分探索

二分探索は半探索とも呼ばれます(バイナリ検索)。これは、データ スケールの対数時間計算量内で検索を完了できる、より効率的な検索方法です。これは、順序付けされた配列内の特定の要素を見つけるための検索アルゴリズムです。

アルゴリズムの考え方

昇順のシーケンスを例として、対象の要素とシーケンスの途中の要素のサイズを比較し、対象の要素がシーケンス内の要素より大きい場合、中間、シーケンスの後半に進みます。二分探索を実行します。対象の要素が中間の位置の要素より小さい場合、配列の前半を比較します。それらが等しい場合、要素の位置は見つかった。各比較の配列の長さは、等しい要素の位置が見つかるかターゲット要素が見つからないまで、前の配列の半分になります。

図

昇順の順序付けされた配列を指定する nums=[-1, 0, 2, 5, 8, 12, 18, 38, 43, 46]

次に、配列内でターゲット値 target = 12 を見つけます。

図は次のとおりです:

##利强综合的链接

ポータル

タイトルの説明:

n 要素で順序付けされた (昇順) 整数配列 nums とターゲット値 target を指定すると、nums でターゲットを検索する関数を作成します。ターゲット値が存在する場合は添字を返し、そうでない場合は -1 を返します。

例 1:

入力: nums = [-1,0,3,5,9,12]、ターゲット = 9

出力: 4
説明: nums に 9 が表示され、添え字は 4

例 2:

入力: nums = [-1,0,3,5,9,12] 、 target = 2

出力: -1
説明: nums に 2 が存在しないため、-1

解決策のアイデア:

の意味によると、-1

が返されます。という質問に対して、「配列は順序付けられた配列である」という答えが得られます。これは、二分探索を使用するための前提条件でもあります。
• 配列の最初と最後の要素をそれぞれ指す 2 つのポインターを定義します;
• 配列の中央の値を検索します; Ifnums [mid] &lt ; target の場合、ターゲットは配列の後半にあり、それ以外の場合、
nums[mid] > target
• は前半にあります; を繰り返します。
nums[mid] = target

まで前のステップを実行します。これは、ターゲットが見つかり、添字が返されたことを示します。

Java コード実装:

class Solution {
    public int search(int[] nums, int target) {
        int left = 0,right = nums.length - 1;
        while(left <= right) { // 循环条件
            int mid = left + (right - left) / 2;
            if(nums[mid] == target){
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;  // 找不到则返回-1
    }
}

複雑さの分析:
• 時間計算量: O(logn)、n は配列の長さです。

空間複雑度: O(1)。

推奨学習: 「

Java ビデオ チュートリアル ###」###

以上がJava 古典アルゴリズム二分探索の原理と実装の図解の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。