Verwenden eine Binäre Suche auf einem int-array in absteigender Reihenfolge sortiert

import java.util.*;
import java.io.*;
import java.util.Arrays;
import java.util.Collections;
import org.apache.commons.lang3.ArrayUtils;
@SuppressWarnings("unused")
public class Tester {
    public static void main(String args[]){
        int i[] = { -7, 15, 21, 22, 43, 49, 51, 67, 81, 84, 89, 95, 97};
        ArrayUtils.reverse(i);
        System.out.println(binarySearch(i, 22));
        System.out.println(binarySearch(i, 89));
        System.out.println(binarySearch(i, -100));
        System.out.println(binarySearch(i, 72));
        System.out.println(binarySearch(i, 102));
    }
    private static int binarySearch(int a[], int srchVal){
        int lb = 0;
        int ub = a.length - 1;

        while(lb <= ub){
            int mid = (lb + ub)/2;
            if(a[mid] == srchVal){
                return mid;
            }
            else if(srchVal > a[mid]){
                lb = mid + 1;
            }
            else{
                ub = mid - 1;
            }
         }
        return -1;
    }
}

Für eine Zuordnung in der Klasse I müssen Sie die Methode binarysearch-Methode, so dass es ordnungsgemäß funktioniert mit dem umgekehrten array. Aber ich kann nicht herausfinden, wie soll ich es ändern.

InformationsquelleAutor Ryuk | 2015-02-02

3

Wenn das array in absteigender Reihenfolge sortiert, binäre Suche kann noch arbeiten, wenn Sie umkehren der Sinn für den Wert alle Vergleiche durchgeführt, indem die search-Algorithmus.

Den ist-gleich-Fall ist immer noch in Ordnung, aber Sie können umkehren der Vergleich in der else if zu einem <. Die else muss nicht geändert werden, weil die else if änderung bedeutet, dass die else block repräsentiert nun die > Zustand.

InformationsquelleAutor rgettman
0

Binärer Suche macht die übernahme der Daten ist bestellt. Wenn das der Fall ist, als man weiß, wenn der Wert des ausgewählten index (mid) geringer ist als der Wert, der Wert muss im Bereich 0..mid-1 - und Umgekehrt.

Falls das array sortiert ist in umgekehrter, weiß man, dass wenn der Wert kleiner ist, dann muss man die Suche im zweiten Teil. Das einzige, was Sie ändern müssen, ist die Bedingung, in der else if:
```
else if(srchVal < a[mid]){ //change < to >
    lb = mid + 1;
}
```
Sagte, dass man besser lässt die Methode ein bisschen allgemeiner, so kann man den Komparator mehr generische als auch:
```
private static<T> int binarySearch(T[] a, Comparator<T> c, T srchVal){
    int lb = 0;
    int ub = a.length - 1;

    while(lb <= ub){
        int mid = (lb + ub)/2;
        int ci = c.compare(a[mid],srchVal);
        if(ci == 0){
            return mid;
        }
        else if(ci < 0){
            lb = mid + 1;
        }
        else{
            ub = mid - 1;
        }
     }
    return -1;
}
```
In den Fall, Sie bieten eine reversed-array, Sie brauchen nur eine Comparator<T> zurückgibt -val mit val den Komparator für das original-array.

InformationsquelleAutor Willem Van Onsem
0

Gibt es einen hack:
1) Reverse ganzen Reihe, so dass es jetzt steigt, um array.
2) binäre Suche und dann finden die passenden index.
3) n-index wird die Antwort sein.
- Es ist viel besser, inverse nur die Bedingung als inverse der ganze array, siehe meine Antwort.
InformationsquelleAutor Nikhil Kumar vats

Binäre Suche Arbeit auf sortierte Sätze. Dein code geht davon aus, dass die Reihenfolge aufsteigend, noch ist es das umgekehrte. Als ein Ergebnis, müssen Sie umkehren, Zustand:

while(lb > ub){

Auf Allgemeinen, könnten Sie nicht wissen über die Richtung:

private static int binarySearch(int a[], int srchVal, boolean isAscending){
    int lb = 0;
    int ub = a.length - 1;

    while((lb <= ub) == isAscending){
        int mid = (lb + ub)/2;
        if(a[mid] == srchVal){
            return mid;
        }
        else if(srchVal > a[mid]){
            lb = mid + 1;
        }
        else{
            ub = mid - 1;
        }
     }
    return -1;
}

und Verwendung aufsteigender Reihenfolge standardmäßig:

private static int binarySearch(int a[], int srchVal){
    return binarySearch(a, srchVal, true);
}

aber absteigende in Ihrem Fall

public static void main(String args[]){
    int i[] = { -7, 15, 21, 22, 43, 49, 51, 67, 81, 84, 89, 95, 97};
    ArrayUtils.reverse(i);
    System.out.println(binarySearch(i, 22), false);
    System.out.println(binarySearch(i, 89), false);
    System.out.println(binarySearch(i, -100), false);
    System.out.println(binarySearch(i, 72), false);
    System.out.println(binarySearch(i, 102), false);
}

InformationsquelleAutor Lajos Arpad

Nur ändern srchVal > a[mid] - Zustand zu srchVal < a[mid]

import java.util.*;

import java.io.*;

import java.util.Arrays;

import java.util.Collections;

public class HelloWorld{

    private static int binarySearch(int a[], int srchVal){
        int lb = 0;
        int ub = a.length - 1;

        while(lb <= ub){
            int mid = (lb + ub)/2;
            if(a[mid] == srchVal){
                return mid;
            }
            else if(srchVal < a[mid]){
                lb = mid + 1;
            }
            else{
                ub = mid - 1;
            }
         }
        return -1;
    }

     public static void main(String []args){
         int i[] = {97,95,89,84,81,67,51,49,43,22,21,15,-7};
         System.out.println(binarySearch(i, 22));
         System.out.println(binarySearch(i, 89));
         System.out.println(binarySearch(i, -100));
         System.out.println(binarySearch(i, 72));
         System.out.println(binarySearch(i, 102));
     }
}

InformationsquelleAutor Ram Repaka

0

Können Sie ein reverse-Komparator in die binäre Suche, wenn Sie möchten, führen Sie die binäre Suche in einem array in absteigender Reihenfolge sortiert.
Beispiel:
```
Integer [] arr = new Integer[]{5,6,2,9,7};
Arrays.sort(arr, Collections.reverseOrder()); //sorting the array in descending order
Arrays.binarySearch(arr, 2, Comparator.reverseOrder()) //Searches of for 2 in the array.
```
Die obige Funktion zurück 4. dies ist der index der 2 in umgekehrter sortierten array.
Es funktioniert auch wie gewohnt, wenn das element nicht im array.
Zum Beispiel, wenn Sie die Suche nach Wert 3, wird es wieder -5. (einfügen-index -1)
Überprüfen Sie diese für details.

Dank

InformationsquelleAutor Abhijeet Ankush

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.