I denne artikel vil vi diskutere den binære søgealgoritme. Søgning er processen med at finde et bestemt element på listen. Hvis elementet er til stede på listen, kaldes processen vellykket, og processen returnerer placeringen af dette element. Ellers kaldes søgningen mislykket.
java tostring
Lineær søgning og binær søgning er de to populære søgeteknikker. Her vil vi diskutere den binære søgealgoritme.
Binær søgning er søgeteknikken, der fungerer effektivt på sorterede lister. Derfor, for at søge et element ind i en liste ved hjælp af den binære søgeteknik, skal vi sikre, at listen er sorteret.
Binær søgning følger divide and conquer-tilgangen, hvor listen er opdelt i to halvdele, og emnet sammenlignes med listens midterste element. Hvis matchen er fundet derefter, returneres placeringen af det midterste element. Ellers søger vi ind i en af halvdelene afhængigt af resultatet produceret gennem kampen.
BEMÆRK: Binær søgning kan implementeres på sorterede array-elementer. Hvis listeelementerne ikke er ordnet på en sorteret måde, skal vi først sortere dem.
Lad os nu se algoritmen for binær søgning.
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
Arbejder med binær søgning
Lad os nu se, hvordan den binære søgealgoritme fungerer.
For at forstå, hvordan den binære søgealgoritme fungerer, lad os tage et sorteret array. Det vil være let at forstå, hvordan binær søgning fungerer med et eksempel.
Der er to metoder til at implementere den binære søgealgoritme -
- Iterativ metode
- Rekursiv metode
Den rekursive metode til binær søgning følger opdel og hersk tilgangen.
Lad elementerne i array være -
Lad elementet at søge er, K = 56
Vi skal bruge nedenstående formel til at beregne midt af arrayet -
mid = (beg + end)/2
Så i det givne array -
array.sort i java
tigge = 0
ende = 8
midt = (0 + 8)/2 = 4. Så 4 er midten af arrayet.
Nu er elementet, der skal søges, fundet. Så algoritmen vil returnere indekset for det matchede element.
Binær søgning kompleksitet
Lad os nu se tidskompleksiteten af binær søgning i bedste tilfælde, gennemsnitligt tilfælde og værste tilfælde. Vi vil også se rumkompleksiteten af binær søgning.
1. Tidskompleksitet
| Sag | Tidskompleksitet |
|---|---|
| Bedste sag | O(1) |
| Gennemsnitlig tilfælde | O(logn) |
| Worst Case | O(logn) |
2. Rumkompleksitet
| Rumkompleksitet | O(1) |
- Rumkompleksiteten af binær søgning er O(1).
Implementering af binær søgning
Lad os nu se programmerne for binær søgning på forskellige programmeringssprog.
Program: Skriv et program til at implementere binær søgning i C-sprog.
#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)> Produktion
Så det handler om artiklen. Håber artiklen vil være nyttig og informativ for dig.