In questo articolo discuteremo del programma C per cercare un elemento in un array con i suoi diversi modi ed esempi.
Cos'è un array?
UN struttura dati chiamato un vettore contiene una serie di lunghezza fissa di elementi di tipo identico. Viene spesso utilizzato per archiviare e manipolare raccolte di dati poiché l'indicizzazione consente un accesso efficiente.
Esempio: intnumbers[] = {10, 20, 30, 40, 50};
Ricerca di un elemento in un array
Una tipica operazione nella programmazione del computer è la ricerca di un particolare elemento in un array. L'efficienza del tuo codice può essere notevolmente migliorata utilizzando algoritmi di ricerca efficienti sia che tu stia cercando l'esistenza di un determinato valore individuando l'indice di un elemento o verificando se un elemento esiste. In questo articolo verranno discussi i numerosi metodi per cercare elementi in un array utilizzando il linguaggio di programmazione C.
Esistono principalmente due modi per cercare un elemento in un array:
1. Ricerca lineare
Viene chiamata una strategia di ricerca semplice utilizzata per individuare un dato elemento in un array o elenco ricerca lineare , a volte indicato come ricerca sequenziale . Funziona confrontando ciascun membro dell'array con il valore di destinazione per trovare a incontro O attraversare l'intero array in modo iterativo.
I passaggi fondamentali nella ricerca lineare sono i seguenti:
- Il valore target dovrebbe essere confrontato con l'elemento corrente.
- La ricerca ha esito positivo se l'elemento corrente corrisponde al valore richiesto e quindi l'algoritmo può restituire l'indice dell'elemento o qualsiasi altro output desiderato.
- Vai all'elemento successivo nell'array se l'elemento corrente non corrisponde al valore desiderato.
- Finché non viene stabilita una corrispondenza o non viene raggiunta la fine dell'array, ripetere i passaggi 2-4.
Programma:
#include int linearSearch(int arr[], int n, int target) { for (int i = 0; i<n; i++) { if (arr[i]="=" target) return i; the index target is found } -1; -1 not int main() arr[]="{5," 2, 8, 12, 3}; n="sizeof(arr)" sizeof(arr[0]); calculate number of elements in array result="linearSearch(arr," n, target); (result="=" -1) printf('element found
'); else at %d
', result); 0; < pre> <p> <strong>Output:</strong> </p> <pre> An element found at index 2 </pre> <h3>2. Binary Search</h3> <p>The <strong> <em>binary search</em> </strong> technique is utilized to quickly locate a specific element in a sorted <strong> <em>array</em> </strong> or <strong> <em>list</em> </strong> . It uses a <strong> <em>divide-and-conquer</em> </strong> <strong> <em>strategy</em> </strong> , periodically cutting the search area in half until the target element is located or found to be absent.</p> <p>This is how binary search functions:</p> <ol class="points"> <li>Have a sorted array or list as a base.</li> <li>Establish two pointers, <strong> <em>left</em> </strong> and <strong> <em>right</em> </strong> , with their initial values pointing to the array's first and end members.</li> <li>Use <strong> <em>(left + right) / 2</em> </strong> to get the index of the center element.</li> <li>Compare the target value to the middle element. <ol class="pointsa"> <li>The search is successful if they are equal, and then the program can return the <strong> <em>index</em> </strong> or any other required result.</li> <li>The right pointer should be moved to the element preceding the <strong> <em>middle element</em> </strong> if the middle element is greater than the target value.</li> <li>Move the <strong> <em>left pointer</em> </strong> to the element following the <strong> <em>middle element</em> </strong> if the middle element's value is less than the target value.</li> </ol></li> <li>Steps <strong> <em>3</em> </strong> and <strong> <em>4</em> </strong> should be repeated until the target element is located or the left pointer exceeds the right pointer.</li> <li>The desired element is not in the array if it cannot be located.</li> </ol> <p> <strong>Program:</strong> </p> <pre> #include int binarySearch(int arr[], int left, int right, int target) { while (left <= right) { int mid="left" + (right-left) 2; if (arr[mid]="=" target) return mid; the index target is found } < left="mid" 1; else right="mid-1;" -1; -1 not main() arr[]="{2," 5, 8, 12, 20, 23, 28}; n="sizeof(arr)" sizeof(arr[0]); calculate number of elements in array result="binarySearch(arr," 0, - 1, target); (result="=" -1) printf('element found
'); at %d
', result); 0; pre> <p> <strong>Output:</strong> </p> <pre> An element found at index 4 </pre> <hr></=></pre></n;> 2. Ricerca binaria
IL ricerca binaria La tecnica viene utilizzata per individuare rapidamente un elemento specifico in un ordinamento vettore O elenco . Utilizza a dividere e conquistare strategia , tagliando periodicamente a metà l'area di ricerca fino a localizzare o riscontrare l'assenza dell'elemento bersaglio.
Ecco come funziona la ricerca binaria:
- Avere un array o un elenco ordinato come base.
- Stabilire due puntatori, Sinistra E Giusto , con i valori iniziali che puntano al primo e al membro finale dell'array.
- Utilizzo (sinistra + destra) / 2 per ottenere l'indice dell'elemento centrale.
- Confronta il valore target con l'elemento centrale.
- La ricerca ha esito positivo se sono uguali e quindi il programma può restituire il file indice o qualsiasi altro risultato richiesto.
- Il puntatore destro dovrebbe essere spostato sull'elemento che precede il elemento centrale se l'elemento centrale è maggiore del valore target.
- Muovi il puntatore sinistro all'elemento che segue il elemento centrale se il valore dell'elemento centrale è inferiore al valore target.
- Passi 3 E 4 dovrebbe essere ripetuto finché non viene individuato l'elemento di destinazione o il puntatore sinistro supera il puntatore destro.
- L'elemento desiderato non è nell'array se non può essere individuato.
Programma:
#include int binarySearch(int arr[], int left, int right, int target) { while (left <= right) { int mid="left" + (right-left) 2; if (arr[mid]="=" target) return mid; the index target is found } < left="mid" 1; else right="mid-1;" -1; -1 not main() arr[]="{2," 5, 8, 12, 20, 23, 28}; n="sizeof(arr)" sizeof(arr[0]); calculate number of elements in array result="binarySearch(arr," 0, - 1, target); (result="=" -1) printf(\'element found
\'); at %d
\', result); 0; pre> <p> <strong>Output:</strong> </p> <pre> An element found at index 4 </pre> <hr></=>