In dit artikel bespreken we het binaire zoekalgoritme. Zoeken is het proces waarbij een bepaald element in de lijst wordt gevonden. Als het element aanwezig is in de lijst, wordt het proces succesvol genoemd en retourneert het proces de locatie van dat element. Anders wordt de zoekopdracht mislukt genoemd.
Lineair zoeken en binair zoeken zijn de twee populaire zoektechnieken. Hier zullen we het binaire zoekalgoritme bespreken.
Binair zoeken is de zoektechniek die efficiënt werkt op gesorteerde lijsten. Als we een element in een bepaalde lijst willen doorzoeken met de binaire zoektechniek, moeten we er dus voor zorgen dat de lijst gesorteerd is.
Binair zoeken volgt de verdeel-en-heers-aanpak, waarbij de lijst in twee helften wordt verdeeld en het item wordt vergeleken met het middelste element van de lijst. Als de match wordt gevonden, wordt de locatie van het middelste element geretourneerd. Anders zoeken we in een van de helften, afhankelijk van het resultaat van de wedstrijd.
NPM-cache wissen
OPMERKING: Binair zoeken kan worden geïmplementeerd op gesorteerde array-elementen. Als de lijstelementen niet gesorteerd zijn, moeten we ze eerst sorteren.
Laten we nu eens kijken naar het algoritme van Binary Search.
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
Werking van binair zoeken
Laten we nu eens kijken naar de werking van het binaire zoekalgoritme.
Om de werking van het binaire zoekalgoritme te begrijpen, nemen we een gesorteerde array. Het zal gemakkelijk zijn om de werking van binair zoeken te begrijpen met een voorbeeld.
Er zijn twee methoden om het binaire zoekalgoritme te implementeren:
- Iteratieve methode
- Recursieve methode
De recursieve methode van binair zoeken volgt de verdeel-en-heers-aanpak.
mb naar gb
Laat de elementen van array zijn -
Laat het element om te zoeken is, K = 56
We moeten de onderstaande formule gebruiken om de te berekenen midden van de reeks -
mid = (beg + end)/2
Dus in de gegeven array -
smeken = 0
einde = 8
dfs-algoritme
midden = (0 + 8)/2 = 4. 4 is dus het midden van de array.
Nu is het te zoeken element gevonden. Het algoritme retourneert dus de index van het overeenkomende element.
Complexiteit van binaire zoekopdrachten
Laten we nu eens kijken naar de tijdscomplexiteit van binair zoeken in het beste geval, het gemiddelde geval en het slechtste geval. We zullen ook de ruimtelijke complexiteit van binair zoeken zien.
1. Tijdcomplexiteit
| Geval | Tijdcomplexiteit |
|---|---|
| Beste geval | O(1) |
| Gemiddeld geval | O(login) |
| Het slechtste geval | O(login) |
2. Ruimtecomplexiteit
| Ruimtecomplexiteit | O(1) |
- De ruimtecomplexiteit van binair zoeken is O(1).
Implementatie van binair zoeken
Laten we nu de programma's van Binary Search in verschillende programmeertalen bekijken.
Programma: Schrijf een programma om binair zoeken in C-taal te implementeren.
jaar maand
#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)> Uitvoer
Dus dat is alles over het artikel. Ik hoop dat het artikel nuttig en informatief voor u zal zijn.