TechCodeview

En rask metode for å finne et bestemt element i en sortert matrise er et binært søk. Den første oppgaven til denne algoritmen er å sammenligne målverdien med arrayens midtelement. Søket anses som vellykket hvis målverdien finnes i midtelementet. Algoritmen vil se i venstre halvdel av matrisen hvis målverdien er mindre enn midtelementet. Programmet vil skanne høyre halvdel av matrisen hvis målverdien er større enn midtelementet. Denne metoden gjentas til enten målverdien eller søkeområdet er oppbrukt.

Bruk:

Databaser, søkemotorer og databehandling er bare noen av applikasjonene som bruker den binære søkestrategien.

Kjennetegn:

• Matrisen med inngangsverdier må sorteres.
• Med hver iterasjon krymper metoden søkeområdet med det halve, noe som gjør den spesielt effektiv for store datasett.
• Algoritmen har en O (log n) worst-case tidskompleksitet.
• Å finne ønsket verdi gjøres av programmet ved å bruke en del-og-hersk-strategi.

Her er et enkelt eksempel på den binære søkealgoritmen skrevet i C:

 #include int binary_search(int arr[], int left, int right, int target) { while (left <= right) { int mid="left" + (right - left) 2; if (arr[mid]="=" target) return mid; } else < left="mid" 1; right="mid" -1; target not found main() arr[]="{1," 3, 5, 7, 9}; n="sizeof(arr)" sizeof(arr[0]); index="binary_search(arr," 0, 1, target); (index="=" -1) printf('target found
'); at %d
', index); 0; pre> <p> <strong>Output:</strong> </p> <pre> Target found at index 2 </pre> <ul> <li>The binary_search function accepts four arguments: the array to search, the left and right search range boundaries, and the target value to look for. The function returns its index if the desired value can be found; else, it returns -1.</li> <li>The main function creates an array arr and a value target. The binary_search function is then used to search the array for the desired value. The function returns the index where the target value was located if it was, the function returns the index at which it was found. Otherwise, the message &apos;Target not found&apos; is displayed.</li> <li>The binary search algorithm&apos;s implementation is basic. We begin by setting the left border to the array&apos;s initial index and the right boundary to the array&apos;s last index. Once the left boundary is less than or equal to the right border, the array is looped through one more time. We use the formula (left + right) / 2 within the loop to calculate the middle index of the search range. This formula computes the integer value of the middle index&apos;s floor.</li> <li>The centre member of the array is contrasted with the target value. We return the index of the middle element if they are equal. We change the right boundary to be one less than the middle index if the desired value is less than the middle element. If not, we adjust the left border so that it is one more than the centre index. We continue doing this until the goal value is obtained or the search space is filled.</li> <li>The temporal complexity of the binary search algorithm, where n is the array size, is O(log n). This is far more efficient than linear search, which has a temporal complexity of O(n), where n is the size of the array.</li> <li>Finally, the binary search technique offers a useful way to locate a particular member in a sorted array. It is easy to build and has an O(log n) time complexity, making it an efficient approach for large datasets.</li> </ul> <h3>Advantages:</h3> <ul> <li>For large datasets, the binary search algorithm is exceptionally efficient, and it is capable of handling a wide range of input sizes.</li> <li>The algorithm is simple to implement in almost all programming languages.</li> </ul> <h3>Disadvantages:</h3> <ul> <li>Before using the binary search technique, the input array must be sorted, which takes more time and memory.</li> <li>The algorithm cannot be applied to unsorted arrays.</li> <li>The algorithm may yield inaccurate results if the input array is not sorted.</li> <li>The binary search algorithm is not appropriate for tiny datasets since the technique&apos;s overhead may outweigh its benefits.</li> </ul> <h2>Conclusion:</h2> <p>A sorted array can be quickly searched for a specific element using the binary search technique. It employs a divide-and-conquer strategy to cut the search range in half with each iteration, allowing it to be highly efficient for large datasets. However, before using the binary search technique, the input array must be sorted, which takes extra time and memory. The binary search algorithm is a sophisticated data processing tool that is widely utilised in various sectors.</p> <hr></=>

• Binary_search-funksjonen aksepterer fire argumenter: matrisen som skal søkes, venstre og høyre søkeområdegrenser og målverdien å se etter. Funksjonen returnerer sin indeks hvis den ønskede verdien kan bli funnet; ellers returnerer den -1.
• Hovedfunksjonen oppretter en array arr og et verdimål. Binary_search-funksjonen brukes deretter til å søke i matrisen etter ønsket verdi. Funksjonen returnerer indeksen der målverdien var plassert hvis den var, funksjonen returnerer indeksen der den ble funnet. Ellers vises meldingen 'Mål ikke funnet'.
• Implementeringen av den binære søkealgoritmen er grunnleggende. Vi begynner med å sette venstre kant til matrisens innledende indeks og høyre grense til matrisens siste indeks. Når den venstre grensen er mindre enn eller lik den høyre grensen, sløyfes matrisen en gang til. Vi bruker formelen (venstre + høyre) / 2 innenfor løkken for å beregne den midtre indeksen til søkeområdet. Denne formelen beregner heltallsverdien til den midterste indeksens etasje.
• Det midterste medlemmet av matrisen kontrasteres med målverdien. Vi returnerer indeksen til midtelementet hvis de er like. Vi endrer den høyre grensen til å være en mindre enn midtindeksen hvis ønsket verdi er mindre enn midtelementet. Hvis ikke, justerer vi venstre kant slik at den er én mer enn midtindeksen. Vi fortsetter med dette til målverdien er oppnådd eller søkerommet er fylt.
• Den tidsmessige kompleksiteten til den binære søkealgoritmen, der n er matrisestørrelsen, er O(log n). Dette er langt mer effektivt enn lineært søk, som har en tidskompleksitet på O(n), der n er størrelsen på matrisen.
• Til slutt tilbyr den binære søketeknikken en nyttig måte å finne et bestemt medlem i en sortert matrise. Det er enkelt å bygge og har en O(log n) tidskompleksitet, noe som gjør det til en effektiv tilnærming for store datasett.

Fordeler:

• For store datasett er den binære søkealgoritmen eksepsjonelt effektiv, og den er i stand til å håndtere et bredt spekter av inngangsstørrelser.
• Algoritmen er enkel å implementere i nesten alle programmeringsspråk.

Ulemper:

• Før du bruker den binære søketeknikken, må inndatamatrisen sorteres, noe som tar mer tid og minne.
• Algoritmen kan ikke brukes på usorterte arrays.
• Algoritmen kan gi unøyaktige resultater hvis inndatamatrisen ikke er sortert.
• Den binære søkealgoritmen er ikke egnet for små datasett siden teknikkens overhead kan oppveie fordelene.

Konklusjon:

En sortert matrise kan raskt søkes etter et spesifikt element ved å bruke den binære søketeknikken. Den bruker en del-og-hersk-strategi for å halvere søkeområdet med hver iterasjon, slik at det kan være svært effektivt for store datasett. Men før du bruker den binære søketeknikken, må inndatamatrisen sorteres, noe som tar ekstra tid og minne. Den binære søkealgoritmen er et sofistikert databehandlingsverktøy som er mye brukt i ulike sektorer.