Utilizzando binario Cerca con array ordinato con i duplicati

Question

Sono stato incaricato con la creazione di un metodo che stampare tutti gli indici in cui il valore x viene trovato in un array ordinato.

I capire che se solo digitalizzato attraverso la matrice da 0 a N (lunghezza di array) avrebbe una durata di O (n) caso peggiore. Dato che la matrice che verrà passata nel metodo verrà ordinata, suppongo che io possa sfruttare l'utilizzo di una ricerca binaria poiché questa sarà O (log n). Tuttavia, questo funziona solo se l'array ha valori univoci. Poiché la ricerca binaria termina dopo il primo "ritrovamento" di un determinato valore. Stavo pensando di fare una ricerca binaria per trovare x nell'array ordinato e quindi controllare tutti i valori prima e dopo questo indice, ma se l'array conteneva tutti i valori x, non sembra che sarebbe molto meglio.

Credo che quello che sto chiedendo è: esiste un modo migliore per trovare tutti gli indici per un particolare valore in un array ordinato che è meglio di O (n)?

public void PrintIndicesForValue42(int[] sortedArrayOfInts) 
{ 
    // search through the sortedArrayOfInts 

    // print all indices where we find the number 42. 
} 

Es: SortedArray = {1, 13, 42, 42, 42, 77, 78} stamperebbe: "42 è stato trovato a Indici: 2, 3, 4"

Answer 1

Beh, se si in realtà hanno un array ordinato, puoi fare una ricerca binaria finché non trovi uno degli indici che stai cercando, e da lì, il resto dovrebbe essere facile da trovare dato che sono tutti vicini l'uno all'altro.

una volta che hai trovato il tuo primo, che si va a trovare tutte le istanze prima di esso, e quindi tutte le istanze dopo di esso.

Utilizzando questo metodo si dovrebbe ottenere circa O (lg (n) + k) dove k è il numero di occorrenze del valore che si sta cercando.

EDIT:

E, no, non si sarà mai in grado di accedere a tutti i k valori in qualcosa di meno di O (k) tempo.

Seconda modifica: modo che io possa sentire come se in realtà sto contribuendo qualcosa di utile:

Invece di limitarsi a cercare i primi e gli ultimi avvenimenti di X di quanto si possa fare un ricerca binaria per la prima occorrenza e una ricerca binaria per l'ultima occorrenza. che comporterà O (lg (n)) totale. una volta che hai fatto, saprete che tutto il tra gli indici contengono anche X (supponendo che è allineati)

È possibile farlo effettuando una ricerca controllando se il valore è pari a x, E controllo se il valore a sinistra (oa destra a seconda se siete alla ricerca per la prima occorrenza o l'ultima occorrenza) è pari a x.

Answer 2

Un HashMap potrebbe funzionare, se non ti viene richiesto di usare una ricerca binaria.

Creare una HashMap in cui il valore Key è il valore stesso, quindi il valore è un array di indici in cui tale valore si trova nell'array. Passa attraverso l'array, aggiornando ogni array in HashMap per ogni valore.

Il tempo di ricerca degli indici per ciascun valore sarà ~ O (1) e la creazione della mappa stessa sarà ~ O (n).

Answer 3

public void printCopies(int[] array) 
{ 
    HashMap<Integer, Integer> memberMap = new HashMap<Integer, Integer>(); 
    for(int i = 0; i < array.size; i++) 
     if(!memberMap.contains(array[i])) 
      memberMap.put(array[i], 1); 
     else 
     { 
      int temp = memberMap.get(array[i]); //get the number of occurances 
      memberMap.put(array[i], ++temp); //increment his occurance 
     } 

    //check keys which occured more than once 
    //dump them in a ArrayList 
    //return this ArrayList 
} 

in alternanza, invece di contare il numero di occorrenze, si può mettere loro indici in un ArrayList e mettere che nella mappa al posto del conteggio.

HashMap<Integer, ArrayList<Integer>> 
    //the integer is the value, the arraylist a list of their indices 

public void printCopies(int[] array) 
{ 
    HashMap<Integer, ArrayList<Integer>> memberMap = new HashMap<Integer, ArrayList<Integer>>(); 
    for(int i = 0; i < array.size; i++) 
     if(!memberMap.contains(array[i])) 
     { 
      ArrayList temp = new ArrayList(); 
      temp.add(i); 
      memberMap.put(array[i], temp); 
     } 
     else 
     { 
      ArrayList temp = memberMap.get(array[i]); //get the lsit of indices 
      temp.add(i); 
      memberMap.put(array[i], temp); //update the index list 
     } 

    //check keys which return lists with length > 1 
    //handle the result any way you want 
} 

heh, credo che questo dovrà essere pubblicato.

int predefinedDuplicate = //value here; 
int index = Arrays.binarySearch(array, predefinedDuplicate); 
int leftIndex, rightIndex; 
//search left 
for(leftIndex = index; array[leftIndex] == array[index]; leftIndex--); //let it run thru it 
//leftIndex is now the first different element to the left of this duplicate number string 
for(rightIndex = index; array[rightIndex] == array[index]; rightIndex++); //let it run thru it 

//right index contains the first different element to the right of the string 
//you can arraycopy this [leftIndex+1, rightIndex-1] string or just print it 
for(int i = leftIndex+1; i<rightIndex; i++) 
System.out.println(array[i] + "\t"); 

Answer 4

public void PrintIndicesForValue42(int[] sortedArrayOfInts) { 
    int index_occurrence_of_42 = left = right = binarySearch(sortedArrayOfInts, 42); 
    while (left - 1 >= 0) { 
     if (sortedArrayOfInts[left-1] == 42) 
      left--; 
    } 
    while (right + 1 < sortedArrayOfInts.length) { 
     if (sortedArrayOfInts[right+1] == 42) 
      right++; 
    } 
    System.out.println("Indices are from: " + left + " to " + right); 
} 

Questo sarebbe eseguito in O (log (n) + #occurrences) Leggere e comprendere il codice. È abbastanza semplice

Answer 5

Si otterrà il risultato in O (lg n)

public static void PrintIndicesForValue(int[] numbers, int target) { 
    if (numbers == null) 
     return; 

    int low = 0, high = numbers.length - 1; 
    // get the start index of target number 
    int startIndex = -1; 
    while (low <= high) { 
     int mid = (high - low)/2 + low; 
     if (numbers[mid] > target) { 
      high = mid - 1; 
     } else if (numbers[mid] == target) { 
      startIndex = mid; 
      high = mid - 1; 
     } else 
      low = mid + 1; 
    } 

    // get the end index of target number 
    int endIndex = -1; 
    low = 0; 
    high = numbers.length - 1; 
    while (low <= high) { 
     int mid = (high - low)/2 + low; 
     if (numbers[mid] > target) { 
      high = mid - 1; 
     } else if (numbers[mid] == target) { 
      endIndex = mid; 
      low = mid + 1; 
     } else 
      low = mid + 1; 
    } 

    if (startIndex != -1 && endIndex != -1){ 
     for(int i=0; i+startIndex<=endIndex;i++){ 
      if(i>0) 
       System.out.print(','); 
      System.out.print(i+startIndex); 
     } 
    } 
} 

Answer 6

Find_Key(int arr[], int size, int key){ 
int begin = 0; 
int end = size - 1; 
int mid = end/2; 
int res = INT_MIN; 

while (begin != mid) 
{ 
    if (arr[mid] < key) 
     begin = mid; 
    else 
    { 
     end = mid; 
     if(arr[mid] == key) 
      res = mid; 
    } 
    mid = (end + begin)/2; 
} 
return res; 
} 

Assumendo l'array di int è in ordine crescente allineati; Restituisce l'indice del primo indice di occorrenza della chiave o INT_MIN. Corre in O (lg n).

Answer 7

Di seguito si riporta il codice Java, che restituisce l'intervallo per il quale il tasto di ricerca si sviluppa nel dato array ordinato:

public static int doBinarySearchRec(int[] array, int start, int end, int n) { 
    if (start > end) { 
     return -1; 
    } 
    int mid = start + (end - start)/2; 

    if (n == array[mid]) { 
     return mid; 
    } else if (n < array[mid]) { 
     return doBinarySearchRec(array, start, mid - 1, n); 
    } else { 
     return doBinarySearchRec(array, mid + 1, end, n); 
    } 
} 

/** 
* Given a sorted array with duplicates and a number, find the range in the 
* form of (startIndex, endIndex) of that number. For example, 
* 
* find_range({0 2 3 3 3 10 10}, 3) should return (2,4). find_range({0 2 3 3 
* 3 10 10}, 6) should return (-1,-1). The array and the number of 
* duplicates can be large. 
* 
*/ 
public static int[] binarySearchArrayWithDup(int[] array, int n) { 

    if (null == array) { 
     return null; 
    } 
    int firstMatch = doBinarySearchRec(array, 0, array.length - 1, n); 
    int[] resultArray = { -1, -1 }; 
    if (firstMatch == -1) { 
     return resultArray; 
    } 
    int leftMost = firstMatch; 
    int rightMost = firstMatch; 

    for (int result = doBinarySearchRec(array, 0, leftMost - 1, n); result != -1;) { 
     leftMost = result; 
     result = doBinarySearchRec(array, 0, leftMost - 1, n); 
    } 

    for (int result = doBinarySearchRec(array, rightMost + 1, array.length - 1, n); result != -1;) { 
     rightMost = result; 
     result = doBinarySearchRec(array, rightMost + 1, array.length - 1, n); 
    } 

    resultArray[0] = leftMost; 
    resultArray[1] = rightMost; 

    return resultArray; 
} 

Answer 8

sta usando Modified Binary Search. Sarà O (LogN). La complessità spaziale sarà O (1). Chiamiamo BinarySearchModified due volte. Uno per trovare l'indice iniziale dell'elemento e l'altro per trovare l'indice finale dell'elemento.

private static int BinarySearchModified(int[] input, double toSearch) 
    { 
     int start = 0; 
     int end = input.Length - 1; 

     while (start <= end) 
     { 
      int mid = start + (end - start)/2; 
      if (toSearch < input[mid]) end = mid - 1; 
      else start = mid + 1; 
     } 

     return start; 
    } 


    public static Result GetRange(int[] input, int toSearch) 
    { 
     if (input == null) return new Result(-1, -1); 

     int low = BinarySearchModified(input, toSearch - 0.5); 

     if ((low >= input.Length) || (input[low] != toSearch)) return new Result(-1, -1); 

     int high = BinarySearchModified(input, toSearch + 0.5); 

     return new Result(low, high - 1); 
    } 

public struct Result 
    { 
     public int LowIndex; 
     public int HighIndex; 

     public Result(int low, int high) 
     { 
      LowIndex = low; 
      HighIndex = high; 
     } 
    } 

Answer 9

Un altro risultato per log (n) ricerca binaria per il target più a sinistra e il target più a destra. Questo è in C++, ma penso che sia abbastanza leggibile.

L'idea è che finiamo sempre quando left = right + 1. Quindi, per trovare l'obiettivo più a sinistra, se siamo in grado di spostare right al numero più a destra che è inferiore al bersaglio, a sinistra sarà l'obiettivo più a sinistra.

Per più a sinistra di destinazione:

int binary_search(vector<int>& nums, int target){ 
    int n = nums.size(); 
    int left = 0, right = n - 1; 

    // carry right to the greatest number which is less than target. 
    while(left <= right){ 
     int mid = (left + right)/2; 
     if(nums[mid] < target) 
      left = mid + 1; 
     else 
      right = mid - 1; 
    } 
    // when we are here, right is at the index of greatest number 
    // which is less than target and since left is at the next, 
    // it is at the first target's index 
    return left; 
} 

Per il bersaglio più a destra, l'idea è molto simile:

int binary_search(vector<int>& nums, int target){ 
    while(left <= right){ 
     int mid = (left + right)/2; 
     // carry left to the smallest number which is greater than target. 
     if(nums[mid] <= target) 
      left = mid + 1; 
     else 
      right = mid - 1; 
    } 
    // when we are here, left is at the index of smallest number 
    // which is greater than target and since right is at the next, 
    // it is at the first target's index 
    return right; 
} 

Answer 10

mi si avvicinò con la soluzione con ricerca binaria, unica cosa è fare la binaria cerca su entrambi i lati se la partita è stata trovata.

public static void main(String[] args) { 
    int a[] ={1,2,2,5,5,6,8,9,10}; 
    System.out.println(2+" IS AVAILABLE AT = "+findDuplicateOfN(a, 0, a.length-1, 2)); 
    System.out.println(5+" IS AVAILABLE AT = "+findDuplicateOfN(a, 0, a.length-1, 5)); 
    int a1[] ={2,2,2,2,2,2,2,2,2}; 
    System.out.println(2+" IS AVAILABLE AT = "+findDuplicateOfN(a1, 0, a1.length-1, 2)); 

    int a2[] ={1,2,3,4,5,6,7,8,9}; 
    System.out.println(10+" IS AVAILABLE AT = "+findDuplicateOfN(a2, 0, a2.length-1, 10)); 
} 

public static String findDuplicateOfN(int[] a, int l, int h, int x){ 
    if(l>h){ 
     return ""; 
    } 
    int m = (h-l)/2+l; 
    if(a[m] == x){ 
     String matchedIndexs = ""+m; 
     matchedIndexs = matchedIndexs+findDuplicateOfN(a, l, m-1, x); 
     matchedIndexs = matchedIndexs+findDuplicateOfN(a, m+1, h, x); 
     return matchedIndexs; 
    }else if(a[m]>x){ 
     return findDuplicateOfN(a, l, m-1, x); 
    }else{ 
     return findDuplicateOfN(a, m+1, h, x); 
    } 
} 


2 IS AVAILABLE AT = 12 
5 IS AVAILABLE AT = 43 
2 IS AVAILABLE AT = 410236578 
10 IS AVAILABLE AT = 

Penso che questo stia ancora fornendo i risultati in O (logn) complessità.