Wyszukiwanie przedziału w posortowanej tablicy

Witam!
Załóżmy że mam posortowana tablicę n elementową, wartości mogą się powtarzać.
Taka tablica może wyglądac np tak: [-23,-22, ... , 0, 2, 2, 6, ... , 9, 9, 9, 9, 9, ..., 127, 168, 456, ...].
Założmy że chcę wyszukać przedział w ktorym znajdują się dziewiątki, czyli index pierwszej i ostatniej 9.
Jak efektywnie to zrobić?

Ja robiłem to tak:

1. Wyszukuję binarnie dowolną dziewiątkę.
2. Wiedząc że tablica jest posortowana kolejne dziewiątki moga leżeć po prawej i po lewej stronie.
3. za pomocą dwóch pętli while zliczam dziewiątki po prawej (pierwsza pętla while) i po lewej (druga pętla while).

Jednak jest to zbyt wolne, stąd moje pytanie jak od razu znaleźć przedział dziewiątek za pomocą wyszukiwania binarnego?

Jeśli liczby w tablicy są całkowite, to poszukaj binarnie 9 i 10. Jeżeli 10 jest w tablicy, to problem rozwiązany od razu. Jeśli jej nie ma, to zajrzyj do dokumentacji co zwraca wtedy Arrays.binarySearch().

bogdans napisał(a)

Jeśli liczby w tablicy są całkowite, to poszukaj binarnie 9 i 10.

liczby są całkowite ale nie mam pewności że jest tam liczba 10

bogdans napisał(a)

Jeśli liczby w tablicy są całkowite, to poszukaj binarnie 9 i 10. Jeżeli 10 jest w tablicy, to problem rozwiązany od razu. Jeśli jej nie ma, to zajrzyj do dokumentacji co zwraca wtedy Arrays.binarySearch().

Moge dołączyć jedynie "import java.util.Scanner;"

http://canhazcode.blogspot.com/2012/02/we-need-to-talk-about-binary-search.html

@Mobrock, co ty pieprzysz, zajrzyj do dokumentacji, binarySearch(tablica,10) zwraca (nieco zakamuflowane) miejsce gdzie należy wstawić 10 jeśli 10 nie ma w tablicy.
Druga sprawa, pętla wstecz jest bez sensu, bo binarySearch zwraca indeks pierwszego wystąpienia szukanej liczby,

Pisane z palca :]

import java.util.Arrays;
import java.util.Random;

public class Main {

  public static int searchLower(int[] t, int v) {
    int l = 0;
    int r = t.length - 1;
    while (l != r) {
      final int m = l + (r - l) / 2;
      if (t[m] >= v) {
        r = m;
      } else {
        l = m + 1;
      }
    }
    return l;
  }

  public static int searchUpper(int[] t, int v) {
    int l = 0;
    int r = t.length - 1;
    while (l != r) {
      final int m = l + (r - l + 1) / 2;
      if (t[m] > v) {
        r = m - 1;
      } else {
        l = m;
      }
    }
    return l;
  }

  public static void main(String[] args) {
    final int N = 123456;
    final int K = 123456;
    final int[] a = new int[N];
    Random random = new Random();
    for (int i = 0; i < N; i++) {
      a[i] = random.nextInt(K);
    }
    final int[] b = Arrays.copyOf(a, N);
    Arrays.sort(b);
    for (int value : a) {
      final int lower = searchLower(b, value);
      final int upper = searchUpper(b, value);
      assert (b[lower] == value);
      assert (b[upper] == value);
      assert (lower == 0 || b[lower - 1] < value);
      assert (upper == N - 1 || b[upper + 1] > value);
    }
    for (int i = 0; i < K; i++) {
      final int value = random.nextInt(K * 3) - K;
      final int lower = searchLower(b, value);
      final int upper = searchUpper(b, value);
      assert ((b[0] < value) && (b[N - 1] < value)
              || (b[0] > value) && (b[N - 1] > value)
              || (b[lower] < value) == (b[upper] > value));
    }
  }
}

Pisane z głową ;):

//tab tablica posortowana rosnąco
int first = Arrays.binarySearch(tab,9);
int last = Arrays.binarySearch(tab,10);
if(last<0) //nie znaleziono
{
    last = -last - 2;
}
else
{
    last--;
}

binarySearch
public static int binarySearch(int[] a,
int key)
Searches the specified array of ints for the specified value using the binary search algorithm. The array must be sorted (as by the sort(int[]) method) prior to making this call. If it is not sorted, the results are undefined. If the array contains multiple elements with the specified value, there is no guarantee which one will be found.

Parameters:
a - the array to be searched
key - the value to be searched for
Returns:
index of the search key, if it is contained in the array; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the array: the index of the first element greater than the key, or a.length if all elements in the array are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.

My fault, nie doczytałem dokumentacji. Od czasu do czasu potrzebna mi jest funkcja binarySearch(arr, key), która zwraca pierwsze wystąpienie szukanej wartości (lub liczbę ujemną zawierająca informację gdzie należy wstawić szukaną wartość), więc sobie taką napisałem. Ponieważ jest trochę bardziej skomplikowana niż oryginalna funkcja Javy, to porównałem czasy wykonania. Wykonywana jako metoda lokalna jest szybsza (15%) od Arrays.binarySearch(), wykonywana jako metoda static w klasie narzędziowej Tools jest trochę wolniejsza od Arrays.binarySearch() (10%) jeżeli wyszukiwań jest dużo, jest dramatycznie wolniejsza (15 razy) jeżeli wyszukiwań jest mało.