I den här artikeln kommer vi att diskutera den binära sökalgoritmen. Att söka är processen att hitta ett visst element i listan. Om elementet finns i listan kallas processen framgångsrik, och processen returnerar platsen för det elementet. Annars kallas sökningen misslyckad.
Linjär sökning och binär sökning är de två populära sökteknikerna. Här kommer vi att diskutera den binära sökalgoritmen.
Binär sökning är söktekniken som fungerar effektivt på sorterade listor. För att söka ett element i någon lista med den binära söktekniken måste vi därför se till att listan är sorterad.
Binär sökning följer divide and conquer-metoden där listan är uppdelad i två halvor och objektet jämförs med mittelementet i listan. Om matchningen hittas då, returneras platsen för mittelementet. Annars söker vi in i någon av halvlekarna beroende på resultatet som produceras under matchen.
10 ml till oz
OBS: Binär sökning kan implementeras på sorterade arrayelement. Om listelementen inte är ordnade på ett sorterat sätt måste vi först sortera dem.
Låt oss nu se algoritmen för binär sökning.
Algoritm
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
Fungerar med binär sökning
Låt oss nu se hur den binära sökalgoritmen fungerar.
För att förstå hur den binära sökalgoritmen fungerar, låt oss ta en sorterad array. Det blir lätt att förstå hur binär sökning fungerar med ett exempel.
Det finns två metoder för att implementera den binära sökalgoritmen -
- Iterativ metod
- Rekursiv metod
Den rekursiva metoden för binär sökning följer divide and conquer-metoden.
uppdatera i sql med join
Låt elementen i arrayen vara -
Låt elementet att söka är, K = 56
Vi måste använda formeln nedan för att beräkna mitten av arrayen -
mid = (beg + end)/2
Så, i den givna arrayen -
be = 0
slutet = 8
namnkonvention för java
mitten = (0 + 8)/2 = 4. Så 4 är mitten av arrayen.
Nu hittas elementet att söka. Så algoritmen kommer att returnera indexet för det matchade elementet.
Binär söknings komplexitet
Låt oss nu se tidskomplexiteten för binär sökning i bästa fall, genomsnittligt fall och värsta fall. Vi kommer också att se rymdkomplexiteten hos binär sökning.
1. Tidskomplexitet
| Fall | Tidskomplexitet |
|---|---|
| Bästa fall | O(1) |
| Genomsnittligt fall | O(logga) |
| Värsta fall | O(logga) |
2. Rymdkomplexitet
| Rymdkomplexitet | O(1) |
- Rymdkomplexiteten för binär sökning är O(1).
Implementering av binär sökning
Låt oss nu se programmen för binär sökning på olika programmeringsspråk.
Program: Skriv ett program för att implementera binär sökning i C-språk.
textstorlek i latex
#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 handlar om artikeln. Hoppas artikeln kommer att vara användbar och informativ för dig.