[JAVA] Exercice d'algorithme 6

Find Low or High Index

La description

Renvoie un tableau trié de types entiers et les index les plus bas et les plus élevés où se trouve l'élément spécifié (clé). Renvoie -1 si l'élément spécifié n'est pas dans le tableau. La longueur du tableau se chiffre en millions et permet de nombreux éléments qui se chevauchent.

Exemple

Dans l'exemple suivant, l'indice faible et l'indice élevé sont:

clé: 1 bas = 0 et haut = 0

clé: 2 bas = 1 et haut = 1

clé: 5 bas = 2 et haut = 9

clé: 20 bas = 10 et haut = 10 Screen Shot 2019-12-19 at 7.29.16.png

Conseils

Binary Search

Commentaire

Runtime Complexity Le temps d'exécution est O (logn) car il utilise la recherche binaire. Memory Complexity C'est une constante O (1). Aucune mémoire supplémentaire n'est utilisée. Cependant, si la recherche binaire est implémentée de manière récursive Notez que la pile par appel de fonction utilise implicitement O (logn), mémoire. Cependant, nous nous concentrerons ici sur l'itération.

En pensant

Étant donné que la taille du tableau est en millions, le tableau trié est O (n) avec un index faible et un index élevé. Le balayage linéaire est très inefficace. À la place, avec quelques modifications, utilisez la recherche binaire, Trouvez l'indice bas et l'indice élevé pour une clé particulière.

Regardons l'algorithme pour trouver le faible indice.

  1. À chaque étape, considérez la séquence entre un indice faible et un indice élevé. Il calcule également un indice intermédiaire entre un indice faible et un indice élevé. Screen Shot 2019-12-19 at 8.11.03.png

  2. Si l'élément de mid est supérieur ou égal à key, alors high = mid -1. Notez que même si l'élément de mid est le même que key, son index n'est pas nécessairement l'index le plus bas. Screen Shot 2019-12-19 at 8.12.32.png Screen Shot 2019-12-19 at 8.18.33.png

  3. Si l'élément mid est plus petit que key, la clé n'existe pas dans la plage du premier 0 au mid car le tableau est dans l'ordre croissant. Par conséquent, cela peut être après mi + 1. faible = moyen + 1. Screen Shot 2019-12-19 at 8.19.46.png Screen Shot 2019-12-19 at 8.21.03.png

  4. Si low est supérieur à high, terminez l'itération et les points bas à la première occurrence de key. Renvoie -1 si l'élément de low ne correspond pas à la clé.

Trouver l'indice *** élevé est presque le même que le processus ci-dessus. Voici le code d'implémentation. ** **

la mise en oeuvre

findLowHigh.java


import java.util.List;

public class findLowHigh{

    public int binary_search(List<Integer> arr, int low, int high, int key, boolean search_low){

        while(low <= high) {
            int mid = low + (high - low) / 2;

            if (search_low) {
                if (arr.get(mid) >= key) { // Search the left half for the next
                    high = mid - 1;
                }
                else { // Search the right half for the next
                    low = mid + 1;
                }
            }
            else {
                if (arr.get(mid) <= key) { // Search the left half for the next
                    low = mid + 1;
                }
                else { // Search the right half for the next
                    high = mid - 1;
                }
            }
        }

        if (search_low) {
            if (low == - 1) {
                return low;
            }
            else if (low < arr.size() && arr.get(low) == key) {
                return low;
            }
        } else {
            if (high == -1) {
                return high;
            }
            else if (high < arr.size() && arr.get(high) == key) {
                return high;
            }
        }

        return -1;
    }

    public int find_low_index(List<Integer> arr, int key) {
        return binary_search(arr, 0, arr.size() - 1, key, true);
    }

    public int find_high_index(List<Integer> arr, int key) {
        return binary_search(arr, 0, arr.size() - 1, key, false);
    }
}

Main.java


import java.util.Arrays;
import java.util.List;

public class Main {

    public static void main(String[] args) {

        findLowHigh algorithm = new findLowHigh();

        List<Integer> array = Arrays.asList(1,1,1,2,2,2,2,2,3,3,3,4,4,4,4,5,5,5,6,6,6,6,6,6);
        int key = 5;
        int low = algorithm.find_low_index(array, key);
        int high = algorithm.find_high_index(array, key);
        System.out.println("LowIndex of " + key + " : "+low);
        System.out.println("HighIndex of " + key + " : "+high);

        key = -2;
        low = algorithm.find_low_index(array, key);
        high = algorithm.find_high_index(array, key);
        System.out.println("LowIndex of " + key + " : "+low);
        System.out.println("HighIndex of " + key + " : "+high);
    }
}

Output Screen Shot 2019-12-19 at 8.25.35.png

Recommended Posts

Exercice d'algorithme 6
Gymnastique algorithmique 12
Gymnastique algorithmique 10
Gymnastique algorithmique 3
Gymnastique algorithmique 9
Gymnastique algorithmique 14
Gymnastique algorithmique 2
Gymnastique algorithmique 7
Gymnastique algorithmique 15
Algorithme Python
Gymnastique algorithmique 16
Gymnastique algorithmique 8
Exercices d'algorithme 13
Gymnastique algorithmique 17
Gymnastique algorithmique 18
Gymnastique algorithmique 11
Exercice d'algorithme 5
Gymnastique algorithmique 4
Gymnastique algorithmique 24 sous-ensembles
Mémorandum Python (algorithme)
Algorithme d'apprentissage du dictionnaire
Algorithme de recherche de chaînes