I denne artikkelen vil vi diskutere den binære søkealgoritmen. Søking er prosessen med å finne et bestemt element i listen. Hvis elementet er til stede i listen, kalles prosessen vellykket, og prosessen returnerer plasseringen til det elementet. Ellers kalles søket mislykket.
java tostring
Lineært søk og binært søk er de to populære søketeknikkene. Her vil vi diskutere den binære søkealgoritmen.
Binært søk er søketeknikken som fungerer effektivt på sorterte lister. Derfor, for å søke et element inn i en liste ved å bruke den binære søketeknikken, må vi sørge for at listen er sortert.
Binært søk følger del og hersk-tilnærmingen der listen er delt i to halvdeler, og elementet sammenlignes med det midterste elementet i listen. Hvis treffet blir funnet, returneres plasseringen til midtelementet. Ellers søker vi inn i en av halvdelene avhengig av resultatet produsert gjennom kampen.
MERK: Binært søk kan implementeres på sorterte array-elementer. Hvis listeelementene ikke er ordnet på en sortert måte, må vi først sortere dem.
La oss nå se algoritmen til binært søk.
Algoritme
Binary_Search(a, lower_bound, upper_bound, val) // 'a' is the given array, 'lower_bound' is the index of the first array element, 'upper_bound' is the index of the last array element, 'val' is the value to search Step 1: set beg = lower_bound, end = upper_bound, pos = - 1 Step 2: repeat steps 3 and 4 while beg val set end = mid - 1 else set beg = mid + 1 [end of if] [end of loop] Step 5: if pos = -1 print 'value is not present in the array' [end of if] Step 6: exit
Fungerer med binært søk
La oss nå se hvordan den binære søkealgoritmen fungerer.
For å forstå hvordan den binære søkealgoritmen fungerer, la oss ta en sortert matrise. Det vil være lett å forstå hvordan binært søk fungerer med et eksempel.
Det er to metoder for å implementere den binære søkealgoritmen -
- Iterativ metode
- Rekursiv metode
Den rekursive metoden for binært søk følger skille og hersk-tilnærmingen.
La elementene i array være -
La elementet som skal søkes er, K = 56
Vi må bruke formelen nedenfor for å beregne midten av matrisen -
mid = (beg + end)/2
Så, i den gitte matrisen -
array.sort i java
tigge = 0
slutt = 8
midten = (0 + 8)/2 = 4. Så 4 er midten av matrisen.
Nå er elementet som skal søkes funnet. Så algoritmen vil returnere indeksen til elementet som er matchet.
Binært søk kompleksitet
La oss nå se tidskompleksiteten til binært søk i beste tilfelle, gjennomsnittlig tilfelle og verste tilfelle. Vi vil også se plasskompleksiteten til binært søk.
1. Tidskompleksitet
| Sak | Tidskompleksitet |
|---|---|
| Beste sak | O(1) |
| Gjennomsnittlig sak | O(logn) |
| Worst Case | O(logn) |
2. Romkompleksitet
| Plass kompleksitet | O(1) |
- Romkompleksiteten til binært søk er O(1).
Implementering av binært søk
La oss nå se programmene for binært søk på forskjellige programmeringsspråk.
Program: Skriv et program for å implementere binært søk i C-språk.
#include int binarySearch(int a[], int beg, int end, int val) { int mid; if(end >= beg) { mid = (beg + end)/2; /* if the item to be searched is present at middle */ if(a[mid] == val) { return mid+1; } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if(a[mid] <val) { return binarysearch(a, mid+1, end, val); } * if the item to be searched is greater than middle, then it can only in right subarray else beg, mid-1, -1; int main() a[]="{11," 14, 25, 30, 40, 41, 52, 57, 70}; given array val="40;" value n="sizeof(a)" sizeof(a[0]); size of res="binarySearch(a," 0, n-1, store result printf('the elements are - '); for (int i="0;" < n; i++) printf('%d ', a[i]); printf('
element %d', (res="=" -1) not present array'); at %d position array', res); 0; pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-5.webp" alt="Binary Search Algorithm"> <p> <strong>Program:</strong> Write a program to implement Binary search in C++.</p> <pre> #include using namespace std; int binarySearch(int a[], int beg, int end, int val) { int mid; if(end >= beg) { mid = (beg + end)/2; /* if the item to be searched is present at middle */ if(a[mid] == val) { return mid+1; } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if(a[mid] <val) { return binarysearch(a, mid+1, end, val); } * if the item to be searched is greater than middle, then it can only in right subarray else beg, mid-1, -1; int main() a[]="{10," 12, 24, 29, 39, 40, 51, 56, 70}; given array val="51;" value n="sizeof(a)" sizeof(a[0]); size of res="binarySearch(a," 0, n-1, store result cout<<'the elements are - '; for (int i="0;" < n; i++) cout< <a[i]<<' cout<<'
element '<<val; (res="=" -1) not present array'; at '<<res<<' position 0; pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-6.webp" alt="Binary Search Algorithm"> <p> <strong>Program:</strong> Write a program to implement Binary search in C#.</p> <pre> using System; class BinarySearch { static int binarySearch(int[] a, int beg, int end, int val) { int mid; if(end >= beg) { mid = (beg + end)/2; if(a[mid] == val) { return mid+1; /* if the item to be searched is present at middle */ } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if(a[mid] <val) { return binarysearch(a, mid+1, end, val); } * if the item to be searched is greater than middle, then it can only in right subarray else beg, mid-1, -1; static void main() int[] a="{9," 11, 23, 28, 38, 45, 50, 56, 70}; given array int val="70;" value n="a.Length;" size of res="binarySearch(a," 0, n-1, store result console.write('the elements are - '); for (int i="0;" < n; i++) console.write(a[i] + ' console.writeline(); console.writeline('element (res="=" -1) not present array'); at position pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-7.webp" alt="Binary Search Algorithm"> <p> <strong>Program:</strong> Write a program to implement Binary search in Java.</p> <pre> class BinarySearch { static int binarySearch(int a[], int beg, int end, int val) { int mid; if(end >= beg) { mid = (beg + end)/2; if(a[mid] == val) { return mid+1; /* if the item to be searched is present at middle */ } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if(a[mid] <val) { return binarysearch(a, mid+1, end, val); } * if the item to be searched is greater than middle, then it can only in right subarray else beg, mid-1, -1; public static void main(string args[]) int a[]="{8," 10, 22, 27, 37, 44, 49, 55, 69}; given array val="37;" value n="a.length;" size of res="binarySearch(a," 0, n-1, store result system.out.print('the elements are: '); for (int i="0;" < n; i++) system.out.print(a[i] + ' system.out.println(); system.out.println('element is: (res="=" -1) not present array'); at position pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-8.webp" alt="Binary Search Algorithm"> <p> <strong>Program:</strong> Write a program to implement Binary search in PHP.</p> <pre> = $beg) { $mid = floor(($beg + $end)/2); if($a[$mid] == $val) { return $mid+1; /* if the item to be searched is present at middle */ } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if($a[$mid] <$val) { return binarysearch($a, $mid+1, $end, $val); } * if the item to be searched is greater than middle, then it can only in right subarray else $beg, $mid-1, -1; $a="array(7," 9, 21, 26, 36, 43, 48, 54, 68); given array $val="68;" value $n="sizeof($a);" size of $res="binarySearch($a," 0, $n-1, store result echo 'the elements are: '; for ($i="0;" $i < $n; $i++) ' , $a[$i]; <br>' , 'Element to be searched is: ' , $val; if ($res == -1) echo ' <br>' , 'Element is not present in the array'; else echo ' <br>' , 'Element is present at ' , $res , ' position of array'; ?> </$val)></pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-9.webp" alt="Binary Search Algorithm"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></val)></pre></val)></pre></val)></pre></val)> Produksjon
Så det handler om artikkelen. Håper artikkelen vil være nyttig og informativ for deg.