Wie finde ich den Index eines Elements in einem int-Array?

78

Wie finde ich einen Index eines bestimmten Werts in einem Java-Array vom Typ int?

Ich habe versucht, Arrays.binarySearchauf unserem unsortierten Array zu verwenden, es gibt nur manchmal die richtige Antwort.

Jeomark
quelle
11
Die binäre Suche funktioniert niemals in einem unsortierten Array.
Chris Eberle
Dann kannst du mir etwas vorschlagen, wie soll ich das machen. Denn wenn ich das Array sortiere, verliere ich den Überblick über Indizes und ich muss wissen, von welchem ​​Index der Wert stammt?
Jeomark
EDIT: Ich habe vergessen hinzuzufügen, ich muss Array-Index auch für doppelte Werte finden.
Jeomark
1
Wenn Sie das Array nicht sortieren möchten, verwenden Sie einfach eine einfache for-Schleife, um den Wert zu ermitteln.
Jamie Curtis
2
Es ist im Allgemeinen gut, die Dokumentation der Funktionen zu lesen :) Von binarySearch: "Durchsucht das angegebene Array von ... nach dem angegebenen Wert mit dem binären Suchalgorithmus. Das Array muss zuvor sortiert werden (wie nach der Methode sort (long [])) um diesen Anruf zu machen. Wenn es nicht sortiert ist, werden die Ergebnisse nicht definiert. ...“

Antworten:

130
Integer[] array = {1,2,3,4,5,6};

Arrays.asList(array).indexOf(4);

Beachten Sie, dass diese Lösung threadsicher ist, da ein neues Objekt vom Typ List erstellt wird.

Außerdem möchten Sie dies nicht in einer Schleife oder ähnlichem aufrufen, da Sie jedes Mal ein neues Objekt erstellen würden

Pablo Fernandez
quelle
Danke, aber würde es für Typ Double funktionieren? Entschuldigung, ich habe vergessen, in der Frage zu erwähnen, aber ich muss dies auch für doppelte Werte arbeiten. Es funktioniert jedoch gut mit Ints.
Jeomark
Ja, Sie müssten nichts ändern (aber den Array-Typ offensichtlich)
Pablo Fernandez
54
Eigentlich funktioniert der Code nicht. Überprüfen Sie, warum indexOf das Objekt nicht findet.
Teloon
13
Sie müssen das Array in Integer [] anstelle von int [] konvertieren. primitive Arrays werden nicht autoboxed.
Leon Helmsley
1
Ist das wirklich threadsicher? Wenn ich durch die Quelle klicke, erstellt List.asList () eine ArrayList, die das int-Array direkt als Datencontainer verwendet (nicht kopiert)
Langusten Gustel
26

Eine weitere Option, wenn Sie Guava-Sammlungen verwenden, ist Ints.indexOf

// Perfect storm:
final int needle = 42;
final int[] haystack = [1, 2, 3, 42];

// Spoiler alert: index == 3
final int index = Ints.indexOf(haystack, needle);

Dies ist eine gute Wahl, wenn Platz, Zeit und Code-Wiederverwendung knapp sind. Es ist auch sehr knapp.

Übrigens
quelle
19

Ein Blick auf die API zeigt, dass Sie zuerst das Array sortieren müssen

Damit:

Arrays.sort(array);
Arrays.binarySearch(array, value);

Wenn Sie das Array nicht sortieren möchten:

public int find(double[] array, double value) {
    for(int i=0; i<array.length; i++) 
         if(array[i] == value)
             return i;
}
Jamie Curtis
quelle
7
+1 Es sollte jedoch beachtet werden, dass die Eingabe Arrays.sort mutiert und das ursprüngliche Array geändert wird.
Vielen Dank, die 2. Methode hat mir irgendwie geholfen, nachdem ich eine Logik für doppelte Werte mit unterschiedlichen Indizes hinzugefügt habe.
Jeomark
14

Kopieren Sie diese Methode in Ihre Klasse

 public int getArrayIndex(int[] arr,int value) {

        int k=0;
        for(int i=0;i<arr.length;i++){

            if(arr[i]==value){
                k=i;
                break;
            }
        }
    return k;
}

Rufen Sie diese Methode mit zwei Durchlaufreihen Array und Wert auf und speichern Sie den Rückgabewert in einer Ganzzahlvariablen.

int indexNum = getArrayIndex(array,value);

Vielen Dank

Dalvinder Singh
quelle
7
ArrayUtils.indexOf(array, value);
Ints.indexOf(array, value);
Arrays.asList(array).indexOf(value);
Ashwini Chaudhari
quelle
3
Während dieser Code die Frage lösen kann, einschließlich einer Erklärung, wie und warum dies das Problem löst, würde dies wirklich dazu beitragen, die Qualität Ihres Beitrags zu verbessern, und wahrscheinlich zu mehr Up-Votes führen. Denken Sie daran, dass Sie in Zukunft die Frage für die Leser beantworten, nicht nur für die Person, die jetzt fragt. Bitte bearbeiten Sie Ihre Antwort, um Erklärungen hinzuzufügen und anzugeben, welche Einschränkungen und Annahmen gelten.
Doppel-Piepton
4

Sie können modernes Java verwenden, um dieses Problem zu lösen. Bitte verwenden Sie den folgenden Code:

static int findIndexOf(int V, int[] arr) {
        return IntStream.range(1, arr.length).filter(i->arr[i]==V).findFirst().getAsInt();
    }
Mohammad
quelle
Toll! Danke für das Teilen. Es hilft, sich über die neuen (optimierten) integrierten Lösungen im Kontext der Sprachfähigkeiten zu informieren.
Guillermo Garcia
3

Sie müssen Werte sortieren, bevor Sie die binäre Suche verwenden können. Andernfalls besteht die manuelle Methode darin, alle Ints in Ihrem Tab zu testen.

public int getIndexOf( int toSearch, int[] tab )
{
  for( int i=0; i< tab.length ; i ++ )
    if( tab[ i ] == toSearch)
     return i;

  return -1;
}//met

Eine alternative Methode könnte darin bestehen, alle Indizes für jeden Wert in einer Karte abzubilden.

tab[ index ] = value;
if( map.get( value) == null || map.get( value) > index )
    map.put( value, index );

und dann map.get (Wert), um den Index zu erhalten.

Grüße, Stéphane

@pst, danke für deine Kommentare. Können Sie eine andere alternative Methode posten?

Snicolas
quelle
Das ist eine Möglichkeit, ja. Dies ist jedoch nicht der einzige Weg. Die Verwendung der booleschen Variablen ist foundhier nutzlos (und wird nicht verwendet) und sollte entfernt werden. Ein +1 für die Anzeige der "manuellen Schleifenmethode" (abgesehen von Stil- und Formatierungsproblemen).
2

Einfach:

public int getArrayIndex(int[] arr,int value) {
    for(int i=0;i<arr.length;i++)
        if(arr[i]==value) return i;
    return -1;
}
Gil SH
quelle
2
    Integer[] arr = { 0, 1, 1, 2, 3, 5, 8, 13, 21 };
    List<Integer> arrlst = Arrays.asList(arr);
    System.out.println(arrlst.lastIndexOf(1));
alok
quelle
Beachten Sie, dass das Array Integer [] und nicht int [] sein muss. Zumindest funktioniert indexOf () nur mit Integer
djdance
1

Falls noch jemand nach der Antwort sucht -

  1. Sie können ArrayUtils.indexOf () aus der [Apache Commons Library] [1] verwenden.

  2. Wenn Sie Java 8 verwenden, können Sie auch die Strean-API verwenden:

    public static int indexOf(int[] array, int valueToFind) {
        if (array == null) {
            return -1;
        }
        return IntStream.range(0, array.length)
                .filter(i -> valueToFind == array[i])
                .findFirst()
                .orElse(-1);
    }
    

    [1]: https://commons.apache.org/proper/commons-lang/javadocs/api-3.1/org/apache/commons/lang3/ArrayUtils.html#indexOf(int[‹,%20int)

Deep Shah
quelle
1

Der einfachste Weg ist das Iterieren. Zum Beispiel wollen wir den Mindestwert des Arrays und seinen Index finden:

public static Pair<Integer, Integer> getMinimumAndIndex(int[] array) {
        int min = array[0];
        int index = 0;
        for (int i = 1; i < array.length; i++) {
            if (array[i] < min) {
                min = array[i];
                index = i;
            }

            return new Pair<min, index>;

Auf diese Weise testen Sie alle Array-Werte. Wenn einige davon minimal sind, kennen Sie auch den Mindestindex. Dies kann genauso funktionieren, wenn Sie nach einem Wert suchen:

public static int indexOfNumber(int[] array) {
        int index = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] == 77) {        // here you pass some value for example 77
                index = i;
            }
        }
        return index;
    }
Rafał Pawłowski
quelle
0

Sie können entweder durch das Array gehen, bis Sie den gesuchten Index gefunden haben, oder Liststattdessen einen verwenden. Beachten Sie, dass Sie das Array mit in eine Liste umwandeln können asList().

loswerden
quelle
0
/**
     * Method to get the index of the given item from the list
     * @param stringArray
     * @param name
     * @return index of the item if item exists else return -1
     */
    public static int getIndexOfItemInArray(String[] stringArray, String name) {
        if (stringArray != null && stringArray.length > 0) {
            ArrayList<String> list = new ArrayList<String>(Arrays.asList(stringArray));
            int index = list.indexOf(name);
            list.clear();
            return index;
        }
        return -1;
    }
Manmohan Soni
quelle
Das clearund das new ArrayListsind unnötige Operationen. Das Zuweisen eines neuen ArrayListkopiert das gesamte Array, was sinnlos ist, da Arrays.asListbereits ein Array zurückgegeben wird, das Listeine indexOfMethode hat. Das Löschen der Kopie der Liste ist nicht erforderlich. GC nimmt sie trotzdem weg.
TWiStErRob
0

Sie können es so machen:

 public class Test {

public static int Tab[]  = {33,44,55,66,7,88,44,11,23,45,32,12,95};
public static int search = 23;

public static void main(String[] args) {
    long stop = 0;
    long time = 0;
    long start = 0;
    start = System.nanoTime();
    int index = getIndexOf(search,Tab);
    stop = System.nanoTime();
    time = stop - start;
    System.out.println("equal to took in nano seconds ="+time);
    System.out.println("Index  of searched value is: "+index);
    System.out.println("De value of Tab with searched index is: "+Tab[index]);
    System.out.println("==========================================================");
    start = System.nanoTime();
    int Bindex = bitSearch(search,Tab);
    stop = System.nanoTime();
    time = stop - start;
    System.out.println("Binary search took nano seconds ="+time);
    System.out.println("Index  of searched value is: "+Bindex);
    System.out.println("De value of Tab with searched index is: "+Tab[Bindex]);
}



public static int getIndexOf( int toSearch, int[] tab ){
     int i = 0;
     while(!(tab[i] == toSearch) )
     {  i++; }
       return i; // or return tab[i];
   }
public static int bitSearch(int toSearch, int[] tab){
    int i = 0;
    for(;(toSearch^tab[i])!=0;i++){
    }
    return i;

}

}}

XOR hinzugefügt :)

Andre
quelle
tab.equals(toSearch)vergleicht ein Array mit einem int. Vielleicht tab[i] == toSearchstattdessen.
Mike Samuel
Dies funktioniert danke Mike ... Google für die binäre Suche, einige nette Artikel da draußen und es ist eine interessante Methode
Andre
@Andre wenn Sie versuchen , einen Punkt zu beweisen gibt ihnen gleiche Wettbewerbsbedingungen (gleiche Reihenfolge, gleichen Steuerstrom): while (tab[i] != toSearch) i++;VS while ((tab[i] ^ toSearch) != 0) i++;.
TWiStErRob
1
Auf jeden Fall funktioniert diese Art des Timings nicht, für mich bitSearchist es immer schneller als getIndexOf; während, wenn ich einfach die Aufrufe an die beiden Methoden getIndexOfaustausche, schneller als bitSearch. Dies zeigt deutlich, dass der zweite aus irgendeinem Grund aufgrund von JVM-Interna immer schneller ist. Sie sollten das Experiment viele Male (wahrscheinlich Millionen) wiederholen, die Werte mitteln, Extremwerte verwerfen und ein Aufwärmen durchführen, das dem Test sehr ähnlich ist.
TWiStErRob
0

Bei der Hauptmethode mit for-Schleifen: - Die dritte for-Schleife in meinem Beispiel ist die Antwort auf diese Frage. -In meinem Beispiel habe ich ein Array mit 20 zufälligen Ganzzahlen erstellt, einer Variablen die kleinste Zahl zugewiesen und die Schleife gestoppt, als die Position des Arrays den kleinsten Wert erreicht hat, während ich die Anzahl der Schleifen gezählt habe.

import java.util.Random;
public class scratch {
    public static void main(String[] args){
        Random rnd = new Random();
        int randomIntegers[] = new int[20];
        double smallest = randomIntegers[0];
        int location = 0;

        for(int i = 0; i < randomIntegers.length; i++){             // fills array with random integers
            randomIntegers[i] = rnd.nextInt(99) + 1;
            System.out.println(" --" + i + "-- " + randomIntegers[i]);
        }

        for (int i = 0; i < randomIntegers.length; i++){            // get the location of smallest number in the array 
            if(randomIntegers[i] < smallest){
                smallest = randomIntegers[i];                 
            }
        }

        for (int i = 0; i < randomIntegers.length; i++){                
            if(randomIntegers[i] == smallest){                      //break the loop when array location value == <smallest>
                break;
            }
            location ++;
        }
        System.out.println("location: " + location + "\nsmallest: " + smallest);
    }
}

Code gibt alle Nummern und ihre Positionen sowie die Position der kleinsten Nummer gefolgt von der kleinsten Nummer aus.

Extremoats
quelle
0
static int[] getIndex(int[] data, int number) {
    int[] positions = new int[data.length];
    if (data.length > 0) {
        int counter = 0;
        for(int i =0; i < data.length; i++) {
            if(data[i] == number){
                positions[counter] = i;
                counter++;
            }
        }
    }
    return positions;
}
Rahul9191
quelle
0

Binäre Suche: Die binäre Suche kann auch verwendet werden, um den Index des Array-Elements in einem Array zu finden. Die binäre Suche kann jedoch nur verwendet werden, wenn das Array sortiert ist. Java bietet uns eine eingebaute Funktion, die in der Arrays-Bibliothek von Java zu finden ist. Sie gibt den Index zurück, wenn das Element vorhanden ist, andernfalls wird -1 zurückgegeben. Die Komplexität ist O (log n). Nachfolgend finden Sie die Implementierung der binären Suche.

public static int findIndex(int arr[], int t) { 
   int index = Arrays.binarySearch(arr, t); 
   return (index < 0) ? -1 : index; 
} 
Tushar Pandey
quelle
-2
Integer[] array = {1, 2, 3, 4, 5, 6};

for (int i = 0; i < array.length; i++) {
    if (array[i] == 4) {
        system.out.println(i);
        break;
    }
}
Vani
quelle
3
Doppelte Antwort.
Feindalpfa