Plancher et plafond de X à partir d'un tableau trié

Question

Rechercher l'étage et le plafond d'un nombre X à partir d'un tableau déjà trié. par exemple

a[] = {3, 7, 9, 10, 15}

• si X=2, étage = N/A, plafond = 3
• si X=3, étage = 3, plafond = 3
• si X=4, étage = 3, plafond = 7
• si X=16, étage = 15, plafond = N/A

Je pense que la plupart d'entre nous connaissent la solution, c'est-à-dire, nous pouvons trouver l'étage/le plafond par recherche binaire modifiée. Mais le problème avec la recherche binaire modifiée est que nous devons prendre en compte de nombreuses conditions limites. Mais j'ai découvert que le même algorithme de recherche binaire fonctionne mais pour l'étage, il suffit d'écrire if low > high return low et pour le plafond if low > high return high. Et si l'étage retourne -1 alors afficher N/A et si le plafond retourne une valeur qui est supérieure à l'index du tableau alors afficher N/A.

Algorithme pour l'étage :

int floorSearch(int a[], int low, int high, int x)
{
    if(low > high){
        return low;
    }
    int mid = (low+high)/2;
    if(a[mid]>x){
        return floorSearch(a, low, mid-1, x);
    }
    else if(a[mid]

``

et pour le plafond :

int ceilSearch(int a[], int low, int high, int x)
{
    if(low > high){
        return high;
    }
    int mid = (low+high)/2;
    if(a[mid]>x){
        return ceilSearch(a, low, mid-1, x);
    }
    else if(a[mid]

`

c'est très simple, n'est-ce pas? J'ai vérifié pour de nombreuses entrées et cela fonctionne mais j'ai échoué à prouver la justesse de l'algorithme. Est-ce que quelqu'un peut essayer de prouver la justesse ou vous pouvez également donner une entrée d'exemple pour laquelle cet algorithme échouera. Merci.

` ``

Answer 1

Conseils sur la façon de faire la preuve:

1. Les preuves de correction pour ces algorithmes suivraient la structure récursive des algorithmes; c'est-à-dire en utilisant la preuve par induction structurelle (cherchez).

2. Regardez une preuve pour la recherche binaire standard et essayez de comprendre comment elle est construite.

3. Si votre code contient des bugs, alors vous devriez ne pas réussir à trouver une preuve de correction; consultez d'autres commentaires et d'autres réponses!

Answer 2

Il y a un bug traditionnel dans le code. Il utilise int mid = (low+high)/2;. Si le tableau est très grand, il est possible que l'addition dépasse et donne un résultat négatif, rendant mid négatif.

Le bug peut être corrigé en utilisant int mid = (low+high)>>>1;, comme c'est le cas dans les méthodes de recherche binaire de java.util.Arrays. Le >>> 1 fait, en effet, une division non signée par 2.

Answer 3

Étant donné que vous avez seulement modifié la condition if(low > high), notez ce que cela équivaut dans une recherche binaire normale. Comprendre la preuve de la recherche binaire, déterminer la justesse ici devrait être presque trivial.

Answer 4

Voici un cas de test qui va casser votre code pour ceilSearch.

a={3, 7, 9, 11, 13}, x=10.

Je liste low, high et mid dans chaque appel récursif:

(0, 4, 2) -> a[2]=9 < x

(3, 4, 3) -> a[3]=11 > x

(3, 2, 2) -> low > high, retourner low = 2.

La réponse correcte serait 3, pas 2.

Answer 5

public static int[] floorAndCeil(int cible, int[] arr) {
    int n = arr.length;       
    int[] ans = new int[2];     
    int l=0, r=n-1; 
    while(l<=r){                
            int mid = l+(r-l)/2;            
            if(arr[mid]>cible){
                r=mid-1;
            }else if(arr[mid]