Ricerca binaria

In questo tutorial imparerai come funziona l'ordinamento della ricerca binaria. Inoltre, troverai esempi funzionanti di ricerca binaria in C, C ++, Java e Python.

La ricerca binaria è un algoritmo di ricerca per trovare la posizione di un elemento in un array ordinato.

In questo approccio, l'elemento viene sempre cercato nel mezzo di una porzione di un array.

La ricerca binaria può essere implementata solo su un elenco ordinato di elementi. Se gli elementi non sono già ordinati, dobbiamo prima ordinarli.

Ricerca binaria funzionante

L'algoritmo di ricerca binaria può essere implementato in due modi discussi di seguito.

  1. Metodo iterativo
  2. Metodo ricorsivo

Il metodo ricorsivo segue l'approccio divide et impera.

I passaggi generali per entrambi i metodi sono discussi di seguito.

  1. L'array in cui deve essere eseguita la ricerca è: Initial array
    Sia x = 4l'elemento da cercare.
  2. Impostare due puntatori basso e alto rispettivamente nelle posizioni più bassa e più alta. Impostazione dei puntatori
  3. Trova l'elemento centrale a metà della matrice, ad es. (arr(low + high)) / 2 = 6. Elemento centrale
  4. Se x == mid, restituisce mid.Else, confronta l'elemento da cercare con m.
  5. Se x> mid, confronta x con l'elemento centrale degli elementi sul lato destro del centro. Questo viene fatto impostando basso su low = mid + 1.
  6. Altrimenti, confronta x con l'elemento centrale degli elementi sul lato sinistro del centro. Questo viene fatto impostando alto su high = mid - 1. Trovare l'elemento intermedio
  7. Ripeti i passaggi da 3 a 6 finché il minimo non incontra il massimo. Elemento centrale
  8. x = 4è stato trovato. Trovato

Algoritmo di ricerca binaria

Metodo di iterazione

fare fino a quando i puntatori basso e alto si incontrano. mid = (low + high) / 2 if (x == arr (mid)) return mid else if (x> A (mid)) // x is on the right side low = mid + 1 else // x is on il lato sinistro alto = metà - 1

Metodo ricorsivo

 binarySearch (arr, x, low, high) if low> high return False else mid = (low + high) / 2 if x == arr (mid) return mid else if x <data (mid) // x è sul lato destro return binarySearch (arr, x, mid + 1, high) altrimenti // x è sul lato destro return binarySearch (arr, x, low, mid - 1)

Esempi Python, Java, C / C ++ (metodo iterativo)

Python Java C C ++ 
 # Binary Search in python def binarySearch(array, x, low, high): # Repeat until the pointers low and high meet each other while low <= high: mid = low + (high - low)//2 if array(mid) == x: return mid elif array(mid) < x: low = mid + 1 else: high = mid - 1 return -1 array = (3, 4, 5, 6, 7, 8, 9) x = 4 result = binarySearch(array, x, 0, len(array)-1) if result != -1: print("Element is present at index " + str(result)) else: print("Not found")
 // Binary Search in Java class BinarySearch ( int binarySearch(int array(), int x, int low, int high) ( // Repeat until the pointers low and high meet each other while (low <= high) ( int mid = low + (high - low) / 2; if (array(mid) == x) return mid; if (array(mid) < x) low = mid + 1; else high = mid - 1; ) return -1; ) public static void main(String args()) ( BinarySearch ob = new BinarySearch(); int array() = ( 3, 4, 5, 6, 7, 8, 9 ); int n = array.length; int x = 4; int result = ob.binarySearch(array, x, 0, n - 1); if (result == -1) System.out.println("Not found"); else System.out.println("Element found at index " + result); ) )
 // Binary Search in C #include int binarySearch(int array(), int x, int low, int high) ( // Repeat until the pointers low and high meet each other while (low <= high) ( int mid = low + (high - low) / 2; if (array(mid) == x) return mid; if (array(mid) < x) low = mid + 1; else high = mid - 1; ) return -1; ) int main(void) ( int array() = (3, 4, 5, 6, 7, 8, 9); int n = sizeof(array) / sizeof(array(0)); int x = 4; int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); return 0; )
 // Binary Search in C++ #include using namespace std; int binarySearch(int array(), int x, int low, int high) ( // Repeat until the pointers low and high meet each other while (low <= high) ( int mid = low + (high - low) / 2; if (array(mid) == x) return mid; if (array(mid) < x) low = mid + 1; else high = mid - 1; ) return -1; ) int main(void) ( int array() = (3, 4, 5, 6, 7, 8, 9); int x = 4; int n = sizeof(array) / sizeof(array(0)); int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); )

Esempi Python, Java, C / C ++ (metodo ricorsivo)

Python Java C C ++ 
 # Binary Search in python def binarySearch(array, x, low, high): if high>= low: mid = low + (high - low)//2 # If found at mid, then return it if array(mid) == x: return mid # Search the left half elif array(mid)> x: return binarySearch(array, x, low, mid-1) # Search the right half else: return binarySearch(array, x, mid + 1, high) else: return -1 array = (3, 4, 5, 6, 7, 8, 9) x = 4 result = binarySearch(array, x, 0, len(array)-1) if result != -1: print("Element is present at index " + str(result)) else: print("Not found")
 // Binary Search in Java class BinarySearch ( int binarySearch(int array(), int x, int low, int high) ( if (high>= low) ( int mid = low + (high - low) / 2; // If found at mid, then return it if (array(mid) == x) return mid; // Search the left half if (array(mid)> x) return binarySearch(array, x, low, mid - 1); // Search the right half return binarySearch(array, x, mid + 1, high); ) return -1; ) public static void main(String args()) ( BinarySearch ob = new BinarySearch(); int array() = ( 3, 4, 5, 6, 7, 8, 9 ); int n = array.length; int x = 4; int result = ob.binarySearch(array, x, 0, n - 1); if (result == -1) System.out.println("Not found"); else System.out.println("Element found at index " + result); ) )
 // Binary Search in C #include int binarySearch(int array(), int x, int low, int high) ( if (high>= low) ( int mid = low + (high - low) / 2; // If found at mid, then return it if (array(mid) == x) return mid; // Search the left half if (array(mid)> x) return binarySearch(array, x, low, mid - 1); // Search the right half return binarySearch(array, x, mid + 1, high); ) return -1; ) int main(void) ( int array() = (3, 4, 5, 6, 7, 8, 9); int n = sizeof(array) / sizeof(array(0)); int x = 4; int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); )
 // Binary Search in C++ #include using namespace std; int binarySearch(int array(), int x, int low, int high) ( if (high>= low) ( int mid = low + (high - low) / 2; // If found at mid, then return it if (array(mid) == x) return mid; // Search the left half if (array(mid)> x) return binarySearch(array, x, low, mid - 1); // Search the right half return binarySearch(array, x, mid + 1, high); ) return -1; ) int main(void) ( int array() = (3, 4, 5, 6, 7, 8, 9); int x = 4; int n = sizeof(array) / sizeof(array(0)); int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); )

Complessità di ricerca binaria

Complessità temporali

  • Migliore complessità del caso :O(1)
  • Complessità media del caso :O(log n)
  • Peggiore complessità del caso :O(log n)

Complessità spaziale

La complessità spaziale della ricerca binaria è O(n).

Applicazioni di ricerca binaria

  • Nelle librerie di Java, .Net, C ++ STL
  • Durante il debug, la ricerca binaria viene utilizzata per individuare il punto in cui si verifica l'errore.

Articoli interessanti...