So verwenden Sie die Binärmethode, um die Position von Array-Elementen in Java zu ermitteln

1. Erläuterung der Dichotomiemethode

Die Kernidee der Dichotomiemethode ist die Bewegung des Index, und die Suchgeschwindigkeit erhöht sich geometrisch.

Binäre Suchmethode gibt den Index des gefundenen Array-Elements zurück. Wenn nicht, gibt es -1 zurück.

2. Beispiel:

Binäre Suchmethode lokalisiert die Position des Parameterwerts im Array. Szenariobeschreibung:

Gemäß einem Parameter findet der Wert seinen tiefgestellten Bereich im Array, zum Beispiel: Der Bereich von 2 im Array {0, 1, 3, 5} ist {1, 2}

package com.study.collection;
 
import java.util.Arrays;
 
/**
 * @auth zhangmj
 * @date 2019/2/12 9:14
 */
public class ExampleList<T> {
 
    public static void main(String[] args) {
        int[] intArray = {0,1,2,10,15,20,25,29,31,36,39,40,42,43,46,50,55,60,63,66,70};
        int num =2;
        int[] resultArray = getPostionByTwoPoint(intArray, num);
        System.out.println(Arrays.toString(resultArray));
    }
 
    private static int[] getPostionByTwoPoint(int[] intArray, int num) {
        // 判断
        if(intArray == null || intArray.length == 0){
            throw new RuntimeException("数组不能为空");
        }
        // 定义最小和区间
        if(intArray[0] > num || intArray[intArray.length - 1] < num){
            throw new RuntimeException("不在数组范围之内");
        }
 
        int middle = 0;
        int low = 0;
        int high = intArray.length - 1;
        // 定义首尾特殊的情况
        if(intArray[low] == num){
            int[] resultArray = {low, low};
            return resultArray;
        }else if(intArray[high] == num){
            int[] resultArray = {high, high};
            return resultArray;
        }
        int i = 1;
        // 数在中间的情况
        while(low < high){
            System.out.println("查找第 " + i + " 次");
            middle = (low + high + 1)/2;
            if(intArray[middle] == num){
                int[] resultArray = {middle, middle};
                return resultArray;
            }else if(intArray[middle] > num){
                // num 在 low 和 middle 之间
                int previous = middle - 1;
                if(previous > low  && intArray[previous] < num){
                    int[] resultArray = {previous, middle};
                    return resultArray;
                }
                high = middle;
            }else if(intArray[middle] < num){
                int latter = middle + 1;
                if(latter < high  && intArray[latter] > num){
                    int[] resultArray = {middle, latter};
                    return resultArray;
                }
                low = middle;
            }
            i++;
        }
        throw new RuntimeException("定位异常");
    }
}

Das obige ist der detaillierte Inhalt vonSo verwenden Sie die Binärmethode, um die Position von Array-Elementen in Java zu ermitteln. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!