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

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é.

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.

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.

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