Java 検索の例: 要素を検索するバイナリメソッド (コード)-＆＃＆チュートリアル-php.cn

Java 検索の例: 要素を検索するバイナリメソッド (コード)

不言

リリース： 2018-08-21 14:20:06

オリジナル

2543 人が閲覧しました

この記事の内容は Java の検索例: バイナリメソッドで要素を見つける方法 (コード) です。必要な方は参考にしていただければ幸いです。

二分探索原理の考え方:

検索データは、順序付けされた配列中間要素と比較され、それが中央要素上にある場合は、その左側にあるか右側にあるかが判断されます。右の場合は、最小の検索インデックス値を調整してから次のループに入ります。左の場合は、最大の検索インデックス値を調整してから次のループに入ります。同じ場合は、現在の位置が検索データの位置です。、ループを停止します。

注:

配列に基づいているため、要素間のサイズ関係が要素の検索に使用されるため、配列は順序付き配列である必要があり、コードは昇順です。 (小さい順)、降順(大きい順)も異なります。この記事では昇順を例として取り上げます。

public class Dichotomy {
	
	public static void main(String[] args) {
        int [] array = {1,2,3,4,5};
        int target = 2;//即array[1]
        
        int low = 0;
	int high = array.length - 1;
	while (low <= high) {
	    int middle = (low + high) / 2;
	    if (target > array[middle]) {
	    low = middle + 1;
	    } else if (target < array[middle]) {
		    high = middle - 1;
	    } else {
		    System.out.println(middle);
		    break;
	    }
	}
    }
}

ログイン後にコピー

以下は実行結果です:

それが順序付けされていない配列であり、バイナリメソッドを使用して要素を検索する場合は、最初に配列を並べ替えるだけです。たとえば、バブルソートを使用して昇順 (小さいものから大きいものへ) に並べ替えます。

以下は具体的なコードです:

public class Dichotomy {
	
	public static void main(String[] args) {
        int [] array = {3,2,5,1,4};
        //排序
        int temp = 0;
		for (int time = 1; time < array.length; time++) {
			for (int i = 0; i < array.length-time; i++) {
				if (array[i+1]<array[i]) {
					temp = array[i+1];
					array[i+1] = array[i];
					array[i] = temp;
				}
			}
		}
		for (int i = 0; i < array.length; i++) {
			System.out.println(array[i]);
		}

        //二分法查找
        int target = 2;//即array[1]
        int low = 0;
        int high = array.length - 1;
		
        while (low <= high) {
	        int middle = (low + high) / 2;
	        if (target > array[middle]) {
	        low = middle + 1;
	        } else if (target < array[middle]) {
		        high = middle - 1;
	        } else {
		        System.out.println(middle);
		        break;
	        }
        }
    }
}

ログイン後にコピー

以下は実行結果です: