trova l'indice più basso di un dato valore in una matrice preselezionata

Question

Ehi, ho avuto questa domanda in un'intervista e mi chiedevo quale fosse il modo migliore per risolverlo. Quindi dì che ti viene data una matrice che è già ordinata e vuoi trovare l'indice più basso di qualche valore x.

Ecco un python/pseudocodice di ciò che mi è venuto in mente, mi chiedo solo se c'è un modo migliore per farlo?

def findLowestIndex(arr, x): 
    index = binarySearch(0, len(arr), x) 
    if index != -1: 
     while index > 0: 
      if arr[index] == arr[index-1]: 
       index -= 1 
      else: 
       break 
    return index 

Grazie!

Answer 1

Il tuo metodo richiede tempo lineare nel caso peggiore, che è quando il conteggio di x s nell'array è O (n).

Un O (lg n) soluzione può essere ottenuta modificando la ricerca binaria stessa per trovare il primo x nella matrice invece di uno qualsiasi di essi:

def binary_search(x, a): 
    lo = 0 
    hi = len(a) 

    while lo < hi: 
     mid = (lo + hi) // 2 

     if a[mid] < x: 
      lo = mid + 1 
     elif a[mid] > x: 
      hi = mid 
     elif mid > 0 and a[mid-1] == x: 
      hi = mid 
     else: 
      return mid 

    return -1 

Answer 2

import bisect 
l = [1,2,3,4,4,4,4,4,5,5,5,5,5,6,6,7,7,7,8,8] 
bisect.bisect_left(l, 4) 

EDIT: Ho appena manca una cosa. il bisect ti darà un punto di inserimento. quindi se x non è nella lista avremo comunque un indice dei risultati. Quindi è necessario controllare se x è nella lista prima:

if x in l: 
    .... 

ma per questione intervista, si può decidere di vedere come si arriva con l'algoritmo invece di utilizzare la libreria ...

Answer 3

I Scommetto che il commento di gddc è la risposta più rapida per Python. In caso contrario, l'algoritmo generale è corretto, tranne per il fatto che in alcuni casi è possibile battere il comportamento O (log n) della ricerca binaria. In particolare, nel caso di interi il miglior comportamento nel caso peggiore si può ottenere è O (sqrt (log n)): https://stackoverflow.com/questions/4057258/faster-than-binary-search-for-ordered-list

Answer 4

Se gli elementi sono interi - o enumerati, puoi farlo un po 'più veloce:

Nota che nella ricerca binaria [l'algoritmo, non la funzione python], se un elemento non esiste - puoi trovare l'elemento più piccolo che è più grande quindi l'indice.

1. prima ricerca di x - e ottenere l'indice, che sia i.
2. successivo, cercare x-1. Se non è presente nell'elenco, la ricerca binaria può trovarti il ​​primo indice se x.
3. Se è nella lista, lasciare che l'indice Sii j:
   • Fare una ricerca binaria sul sottolista j-i, e la ricerca di un elemento tale che list[k] < list[k+1]

Per i valori non enumerati, è possibile farlo anche con la stessa idea di intervalli decrescenti mentre list[k] < list[k+1] and list[k+1] == x ma trovo più semplice capire prima come viene eseguito per i numeri interi e quindi applicarlo per la soluzione generale.

Si noti che questa soluzione è O(logn), mentre la soluzione banale che proponete è O(n), in lista con un sacco di creduloni, a causa del passo iterativo dopo la ricerca binaria.

Answer 5

Se x non è in X tale che f(x) = v la risposta è banale: ricerca binaria per scoprirlo.

Se c'è uno x tale che f(x) = v allora la risposta è anche banale: ricerca binaria per scoprirlo.

Il problema è interessante solo se sono presenti più x tali che f(x) = v. Se c'è un numero costante di x allora algoritmicamente una ricerca binaria è ottimale. Basta una ricerca binaria e controlla gli indici più bassi in sequenza.

E se, tuttavia, ci sono molti di questi x? Una ricerca sequenziale del genere non è ovviamente ottimale. Infatti, se ci sono c * |X|x allora questo viene eseguito in O(|X|).

Invece cosa si potrebbe fare è inizializzare lbound-0 e ricerca binaria fino a trovare l'elemento, a i, dove ogni volta che si va a destra, aggiornare lbound alla metà che è stato appena utilizzato. Quindi ricerca binaria da [lbound, i - 1]. Fallo fino al i == lbound o non trovi un elemento. Se il primo si verifica, l'indice desiderato è 0. Se si verifica quest'ultimo, l'indice desiderato è il precedente i utilizzato. Il caso peggiore è l'indice desiderato è 0.

La cosa interessante è che funziona ancora nel tempo log(|X|), penso.

Answer 6

Modificare la ricerca binaria per trovare qualsiasi occorrenza di x per la prima volta.

Answer 7

deferred detection of equality approach in binary search fornisce l'indice più piccolo, riducendo i rami di uguaglianza.

def binary_search(low, high, target, array): 
    while low < high: 
     mid = low + (high - low)/2 
     if a[mid] < target: 
      low = mid + 1 
     else: 
      high = mid 

    if (array[low] == target) return low 
    else return -1