W sortowanej tablicy można użyć binarnego wyszukiwania, aby wykonać wiele różnych rodzajów operacji:

  1. Aby znaleźć pierwszy element mniejszy niż cel
  2. znaleźć pierwszy element większy niż cel lub,
  3. Aby znaleźć pierwszy element mniejszy lub równy niż cel
  4. znaleźć pierwszy element większy lub równy niż cel lub nawet konkretny
  5. znaleźć element najbliższego celu.

Możesz znaleźć odpowiedzi na # 2 i # 5 w przepełnieniu stosu, odpowiedź, której odpowiedź wykorzystują mutacje wyszukiwania binarnego, jednak nie ma stałego algorytmu, aby odpowiedzieć na te pytania, w szczególności w dostosowywaniu indeksów.

Na przykład, w pytaniu 3, znajdź pierwszy mniejszy lub równy element w sortowanej tablicy niż cel: Biorąc pod uwagę int[] stocks = new int[]{1, 4, 3, 1, 4, 6};, chcę znaleźć pierwszy element mniejszy niż 5. Powinien zwrócić 4 po sortowaniu, a mój kod idzie jak:

private static int findMin(int[] arr, int target) {
    Arrays.sort(arr);
    int lo = 0;
    int hi = arr.length - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] > target) {
            hi = mid - 1;
        } else {
            lo = mid;
        }
    }
    return lo;
}

Logika jest tutaj:

  1. Jeśli znajdziesz środkowy element równy do celu, właśnie wróciłeś w połowie
  2. Jeśli znajdziesz większy element MID niż cel, wystarczy odrzucić połowę i wszystko większe niż to
  3. Jeśli znajdziesz Mid Element jest mniejszy niż cel, element środkowy może być odpowiedzią, chcesz go zachować, ale odrzucić coś mniejszego niż to.

Jeśli go uruchomisz, wchodzi w nieskończoną pętlę, ale po prostu zmień indeks startowy hi = arr.length - 1 do hi = arr.length;, faktycznie działa dobrze. Nie mam wskazówki, jak naprawdę ustawić wszystkie warunki: jak pisać warunki, co ustawić indeks startowy HI i LO i użyj lo<=hi lub lo < hi.

Jakaś pomoc?

0
Zhen Xu 5 czerwiec 2018, 07:23

4 odpowiedzi

Najlepsza odpowiedź

Zasadniczo w wyżej wymienionym przypadku potrzebujesz największego elementu, który jest mniejszy niż dana wartość, tj. Musisz znaleźć podłogę danego elementu. Można to łatwo zrobić za pomocą wyszukiwania binarnego w O (LOGN), Czas:

Przypadki, które musisz rozważyć, są następujące:

  1. Jeśli ostatni element jest mniejszy niż X, niż zwrot ostatniego elementu.

  2. Jeśli środkowy punkt jest podłogowy, niż w środku.

  3. Jeśli element nie został znaleziony w obu powyższych przypadkach, a jeśli element mieści się między połową a połową -1. Jeśli jest tak, że w połowie 1.
  4. W przeciwnym razie zachowuj go na półto lub w prawo, dopóki nie znajdziesz elementu, który spełnia twój stan. Wybierz prawą połowę lub lewą połowę na podstawie kontroli, którą podana wartość jest większa niż w połowie lub mniej niż w połowie.

Spróbuj wykonać następujące czynności:

static int floorInArray(int arr[], int low, int high, int x)
{
    if (low > high)
        return -1;

    // If last element is smaller than x
    if (x >= arr[high])
        return high;

    // Find the middle point
    int mid = (low+high)/2;

    // If middle point is floor.
    if (arr[mid] == x)
        return mid;

    // If x lies between mid-1 and mid
    if (mid > 0 && arr[mid-1] <= x && x < arr[mid])
        return mid-1;

    // If x is smaller than mid, floor
    // must be in left half.
    if (x < arr[mid])
        return floorInArray(arr, low, mid - 1, x);

    // If mid-1 is not floor and x is
    // greater than arr[mid],
    return floorInArray(arr, mid + 1, high,x);
}
0
amrender singh 12 czerwiec 2018, 08:04

W pętli podczas pętli nie masz zestawu przypadku, gdy hi == lo

Ten przypadek ma zastosowanie, gdy itteruje ostatni element lub macierz ma tylko 1 element.

Ustaw płynę podczas while(lo <= hi) i zakończy się, gdy wszystkie elementy są wyszukiwane

Lub ustawić, jeśli przypadek wewnątrz pętli, gdy hi jest równa lo.

if(hi == lo)
0
Akash Gupta 5 czerwiec 2018, 04:33

Zamiast wdrażać własne wyszukiwanie binarne, możesz po prostu użyć {X0}}, a następnie odpowiednio dostosuj zwracaną wartość.

Zwraca indeks klucza wyszukiwania, jeśli jest zawarty w tablicy; W przeciwnym razie (- ( punkt wstawiania ) - 1). Punkt wkładania jest zdefiniowany jako punkt, w którym klawisz zostanie włożony do tablicy: indeks pierwszego elementu większy niż klucz lub a.length, jeśli wszystkie elementy w tablicy są mniejsze niż Określony klucz. Należy pamiętać, że gwarantuje, że wartość zwracana będzie & gt; = 0, jeśli i tylko wtedy, gdy zostanie znaleziony klucz.

Twoje zasady nie określono, która indeks powrotu, gdy istnieje wiele ważnych wyborów (# 3 lub # 4 z wieloma równymi wartościami lub # 5 z równomiernymi wartościami), więc kod poniżej ma kod, który ma wyraźny wybór. Możesz usunąć dodatkowy kod, jeśli nie dbasz o niejasności lub zmienić logikę, jeśli nie zgadzasz się z moją decyzją, aby rozwiązać go.

Należy pamiętać, że po zwracaniu wartości jest returnValue = -insertionPoint - 1, co oznacza, że insertionPoint = -returnValue - 1, który w kodzie poniżej oznacza -idx - 1. Indeks przed Punkt wstawiania jest zatem -idx - 2.

Metody mogą oczywiście powrócić wartości indeksu poza zakresem ({x0}} lub arr.length), więc dzwoniący zawsze musi sprawdzić. Dla metody closest(), która może się zdarzyć tylko wtedy, gdy macierzysta jest pusta, w którym to przypadku zwraca -1.

public static int smaller(int[] arr, int target) {
    int idx = Arrays.binarySearch(arr, target);
    if (idx < 0) {
        // target not found, so return index prior to insertion point
        return -idx - 2;
    }
    // target found, so skip to before target value(s)
    do {
        idx--;
    } while (idx >= 0 && arr[idx] == target);
    return idx;
}

public static int smallerOrEqual(int[] arr, int target) {
    int idx = Arrays.binarySearch(arr, target);
    if (idx < 0) {
        // target not found, so return index prior to insertion point
        return -idx - 2;
    }
    // target found, so skip to last of target value(s)
    while (idx < arr.length - 1 && arr[idx + 1] == target) {
        idx++;
    }
    return idx;
}

public static int biggerOrEqual(int[] arr, int target) {
    int idx = Arrays.binarySearch(arr, target);
    if (idx < 0) {
         // target not found, so return index of insertion point
        return -idx - 1;
    }
    // target found, so skip to first of target value(s)
    while (idx > 0 && arr[idx - 1] == target) {
        idx--;
    }
    return idx;
}

public static int bigger(int[] arr, int target) {
    int idx = Arrays.binarySearch(arr, target);
    if (idx < 0) {
         // target not found, so return index of insertion point
        return -idx - 1;
    }
    // target found, so skip to after target value(s)
    do {
        idx++;
    } while (idx < arr.length && arr[idx] == target);
    return idx;
}

public static int closest(int[] arr, int target) {
    int idx = Arrays.binarySearch(arr, target);
    if (idx >= 0) {
        // target found, so skip to first of target value(s)
        while (idx > 0 && arr[idx - 1] == target) {
            idx--;
        }
        return idx;
    }
    // target not found, so compare adjacent values
    idx = -idx - 1; // insertion point
    if (idx == arr.length) // insert after last value
        return arr.length - 1; // last value is closest
    if (idx == 0) // insert before first value
        return 0; // first value is closest
    if (target - arr[idx - 1] > arr[idx] - target)
        return idx; // higher value is closer
    return idx - 1; // lower value is closer, or equal distance
}

Testuj

public static void main(String... args) {
    int[] arr = {1, 4, 3, 1, 4, 6};
    Arrays.sort(arr);
    System.out.println(Arrays.toString(arr));

    System.out.println("  |         Index        |        Value        |");
    System.out.println("  |   <  <=   ~  >=   >  |  <  <=   ~  >=   >  |");
    System.out.println("--+----------------------+---------------------+");
    for (int i = 0; i <= 7; i++)
        test(arr, i);
}

public static void test(int[] arr, int target) {
    int smaller        = smaller       (arr, target);
    int smallerOrEqual = smallerOrEqual(arr, target);
    int closest        = closest       (arr, target);
    int biggerOrEqual  = biggerOrEqual (arr, target);
    int bigger         = bigger        (arr, target);
    System.out.printf("%d | %3d %3d %3d %3d %3d  |%3s %3s %3s %3s %3s  | %d%n", target,
                      smaller, smallerOrEqual, closest, biggerOrEqual, bigger,
                      (smaller < 0 ? "" : String.valueOf(arr[smaller])),
                      (smallerOrEqual < 0 ? "" : String.valueOf(arr[smallerOrEqual])),
                      (closest < 0 ? "" : String.valueOf(arr[closest])),
                      (biggerOrEqual == arr.length ? "" : String.valueOf(arr[biggerOrEqual])),
                      (bigger == arr.length ? "" : String.valueOf(arr[bigger])),
                      target);
}

Wyjście

[1, 1, 3, 4, 4, 6]
  |         Index        |        Value        |
  |   <  <=   ~  >=   >  |  <  <=   ~  >=   >  |
--+----------------------+---------------------+
0 |  -1  -1   0   0   0  |          1   1   1  | 0
1 |  -1   1   0   0   2  |      1   1   1   3  | 1
2 |   1   1   1   2   2  |  1   1   1   3   3  | 2
3 |   1   2   2   2   3  |  1   3   3   3   4  | 3
4 |   2   4   3   3   5  |  3   4   4   4   6  | 4
5 |   4   4   4   5   5  |  4   4   4   6   6  | 5
6 |   4   5   5   5   6  |  4   6   6   6      | 6
7 |   5   5   5   6   6  |  6   6   6          | 7
0
Andreas 7 czerwiec 2018, 19:25

Wypróbuj treesets. Jeśli twoje wejście jest tablicy, postępuj zgodnie z poniższymi krokami:

  1. Konwertuj tablicę do zestawu Hash. SRC: https://www.geeksforgeeks.org / Program-to-convert-array-to-set-in-java / 2. Kontert Hash ustawiony na zestaw drzewa. Zestawy drzew przechowywają wartości w sortowanym kolejności bez duplikatów.
  2. Teraz zestawy dzwonek do drzewa, takich jak wyższa (), sufit (), podłogi (), niższe () metody zgodnie z wymaganiami.
0
Likitha Likki 24 wrzesień 2019, 02:27