У овом чланку ћемо разговарати о алгоритму бинарног претраживања. Претраживање је процес проналажења неког одређеног елемента на листи. Ако је елемент присутан на листи, онда се процес назива успешним, а процес враћа локацију тог елемента. У супротном, претрага се назива неуспешном.
Линеарна претрага и бинарна претрага су две популарне технике претраживања. Овде ћемо разговарати о алгоритму бинарног претраживања.
Бинарно претраживање је техника претраживања која ефикасно ради на сортираним листама. Дакле, да бисмо претражили елемент у некој листи користећи технику бинарне претраге, морамо осигурати да је листа сортирана.
Бинарна претрага прати приступ завади па владај у коме се листа дели на две половине, а ставка се пореди са средњим елементом листе. Ако се тада пронађе подударање, враћа се локација средњег елемента. У супротном, тражимо било које од полувремена у зависности од резултата постигнутог током меча.
НАПОМЕНА: Бинарно претраживање се може имплементирати на сортираним елементима низа. Ако елементи листе нису поређани на сортиран начин, прво их морамо сортирати.
Сада, да видимо алгоритам бинарног претраживања.
Алгоритам
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
Рад бинарног претраживања
Сада, да видимо како функционише алгоритам бинарног претраживања.
Да бисмо разумели рад алгоритма бинарног претраживања, узмимо сортирани низ. Биће лако разумети рад бинарног претраживања на примеру.
Постоје два метода за имплементацију алгоритма бинарног претраживања -
- Итеративни метод
- Рекурзивна метода
Рекурзивни метод бинарног претраживања прати приступ завади па владај.
Нека су елементи низа -
Нека је елемент за претрагу, К = 56
Морамо да користимо формулу испод да бисмо израчунали мид низа -
mid = (beg + end)/2
Дакле, у датом низу -
молити = 0
крај = 8
мид = (0 + 8)/2 = 4. Дакле, 4 је средина низа.
Сада је пронађен елемент за претрагу. Дакле, алгоритам ће вратити индекс елемента који се подудара.
Сложеност бинарног претраживања
Сада, да видимо временску сложеност бинарне претраге у најбољем случају, просечном случају и најгорем случају. Видећемо и просторну сложеност бинарног претраживања.
1. Временска сложеност
| Случај | Временска сложеност |
|---|---|
| Најбољи случај | О(1) |
| Авераге Цасе | О(пријава) |
| Најгори случај | О(пријава) |
2. Сложеност простора
| Спаце Цомплекити | О(1) |
- Просторна сложеност бинарног претраживања је О(1).
Имплементација бинарног претраживања
Сада, хајде да видимо програме бинарне претраге у различитим програмским језицима.
Програм: Напишите програм за имплементацију бинарног претраживања у језику Ц.
#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)> Излаз
Дакле, то је све о чланку. Надамо се да ће вам чланак бити користан и информативан.