Recherche binaire sur un tableau avec un préfixe de chaîne

Comment puis-je ajouter les éléments d'un tableau trié contenant un préfixe de chaîne spécifique en utilisant la recherche binaire et ces éléments comme l'ordre dans lequel ils apparaissent dans le tableau à un arrailiste?Recherche binaire sur un tableau avec un préfixe de chaîne

Ce n'est pas difficile à coder mais j'ai de la difficulté avec la recherche binaire. Pour utiliser le préfixe de chaîne, la classe String fournit startswith. J'ai juste besoin d'aide pour démarrer la recherche binaire

public static <T extends Comparable<T>> ArrayList prefixMatch(T[] list, 
      String prefix) { 

}

Source

2012-03-02 Karan Singh

Peut-être pourriez-vous clarifier un peu votre question ... peut-être aussi ajouter un exemple de ce que vous essayez d'obtenir en entrée et en sortie? – mikera

J'ajoute la méthode à compléter ce n'est pas une sorte de revue .. Même s'il y a une liste générique T [] le tableau serait String [] parce que je dois utiliser la recherche binaire pour trouver des éléments dans ce tableau qui commencent par préfixe particulier .. –

duplication possible de [mettre en œuvre la recherche binaire avec le préfixe de chaîne?] (http://stackoverflow.com/questions/9543046/implement-binary-search-with-string-prefix) –

Utilisez la méthode binarySearch de l'API. Ou si vous voulez créer votre propre implémentation de recherche binaire. C'est ici.

/* BinarySearch.java */ 
public class BinarySearch { 
     public static final int NOT_FOUND = -1; 

     public static int search(int[] arr, int searchValue) { 
       int left = 0; 
       int right = arr.length - 1; 
       return binarySearch(arr, searchValue, left, right); 
     } 

     private static int binarySearch(int[] arr, int searchValue, int left, int right) { 
       if (right < left) { 
         return NOT_FOUND; 
       } 
       /* 
       int mid = mid = (left + right)/2; 
       There is a bug in the above line; 
       Joshua Bloch suggests the following replacement: 
       */ 
       int mid = (left + right) >>> 1; 
       if (searchValue > arr[mid]) { 
         return binarySearch(arr, searchValue, mid + 1, right); 
       } else if (searchValue < arr[mid]) { 
         return binarySearch(arr, searchValue, left, mid - 1); 
       } else { 
         return mid; 
       }    
     } 
} 
public class BinarySearchTest { 

     public static void main(String[] args) { 
       int[] arr = {1, 5, 2, 7, 9, 5}; 
       Arrays.sort(arr); 
       System.out.println(BinarySearch.search(arr, 2)); 
     } 
}

Source

2012-03-02 03:02:43 John

merci pour votre aide j'apprécie vraiment mais j'ai besoin d'implémenter une recherche binaire pour un tableau générique (chaîne dans ce cas) qui est trié. Et puis ajoutez les éléments qui commencent par ou contiennent un préfixe particulier à une arraylist inorder comme ils apparaissent dans le tableau générique d'origine –

L'API a 'binarySearch (T [] a, int deIndex, int toIndex, touche T, comparateur c)' méthode. Vous pouvez créer un comparateur et le transmettre pour ne comparer que les préfixes. – John

J'ai eu une exigence similaire - étant donné le tableau de chaînes trouver les index de chaque chaîne qui commence par une nouvelle lettre, à savoir pour Africa Angela Beach Bamboo Zorro, je avais besoin algorithme qui retournerait [ 0, 2, 4 ]

Je trouve qu'il ya un modification de l'algorithme de recherche binaire bien connu qui utilise le test d'égalité différée, ce qui a pour effet secondaire de trouver des index exactement nécessaires - ceux qui commencent la gamme.

Vous pouvez lire à ce sujet dans this Wikipedia article (il y a aussi un exemple très simple basé sur lequel j'ai implémenté le mien).

Source

2013-09-07 22:41:11 dimsuz

Recherche binaire sur un tableau avec un préfixe de chaîne

Répondre

Questions connexes