W tym artykule omówimy algorytm wyszukiwania binarnego. Wyszukiwanie to proces znajdowania określonego elementu na liście. Jeśli element znajduje się na liście, proces nazywa się sukcesem i zwraca lokalizację tego elementu. W przeciwnym razie wyszukiwanie nazywa się niepowodzeniem.
Wyszukiwanie liniowe i wyszukiwanie binarne to dwie popularne techniki wyszukiwania. Tutaj omówimy algorytm wyszukiwania binarnego.
Wyszukiwanie binarne to technika wyszukiwania, która działa efektywnie na posortowanych listach. Dlatego też, aby przeszukać element na jakiejś liście przy użyciu techniki wyszukiwania binarnego, musimy upewnić się, że lista jest posortowana.
Wyszukiwanie binarne opiera się na podejściu „dziel i zwyciężaj”, w którym lista jest dzielona na dwie połowy, a element jest porównywany ze środkowym elementem listy. Jeśli wówczas zostanie znalezione dopasowanie, zwracana jest lokalizacja środkowego elementu. W przeciwnym razie przeszukamy którąkolwiek z połówek w zależności od wyniku osiągniętego w meczu.
UWAGA: Wyszukiwanie binarne można zaimplementować na posortowanych elementach tablicy. Jeśli elementy listy nie są ułożone w sposób posortowany, musimy je najpierw posortować.
Przyjrzyjmy się teraz algorytmowi wyszukiwania binarnego.
Algorytm
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
Działanie wyszukiwania binarnego
Przyjrzyjmy się teraz działaniu algorytmu wyszukiwania binarnego.
Aby zrozumieć działanie algorytmu wyszukiwania binarnego, weźmy posortowaną tablicę. Działanie wyszukiwania binarnego będzie łatwe do zrozumienia na przykładzie.
Istnieją dwie metody implementacji algorytmu wyszukiwania binarnego -
- Metoda iteracyjna
- Metoda rekurencyjna
Rekurencyjna metoda wyszukiwania binarnego opiera się na podejściu dziel i zwyciężaj.
Niech elementami tablicy są -
Niech elementem do przeszukania będzie: K = 56
Aby obliczyć, musimy skorzystać z poniższego wzoru Środek tablicy -
mid = (beg + end)/2
Zatem w podanej tablicy -
błagać = 0
koniec = 8
Środek = (0 + 8)/2 = 4. Zatem 4 jest środkiem tablicy.
Teraz znaleziono element do przeszukania. Zatem algorytm zwróci indeks dopasowanego elementu.
polecenie arp
Złożoność wyszukiwania binarnego
Przyjrzyjmy się teraz złożoności czasowej wyszukiwania binarnego w najlepszym, średnim i najgorszym przypadku. Zobaczymy także złożoność przestrzenną wyszukiwania binarnego.
1. Złożoność czasowa
| Sprawa | Złożoność czasu |
|---|---|
| Najlepszy przypadek | O(1) |
| Przeciętny przypadek | O(zaloguj się) |
| Najgorszy przypadek | O(zaloguj się) |
2. Złożoność przestrzeni
| Złożoność przestrzeni | O(1) |
- Złożoność przestrzenna wyszukiwania binarnego wynosi O (1).
Implementacja wyszukiwania binarnego
Przyjrzyjmy się teraz programom wyszukiwania binarnego w różnych językach programowania.
Program: Napisz program realizujący funkcję wyszukiwania binarnego w języku C.
#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)> Wyjście
To tyle na temat artykułu. Mam nadzieję, że artykuł będzie dla Ciebie pomocny i pouczający.