В тази статия ще обсъдим алгоритъма за двоично търсене. Търсенето е процес на намиране на определен елемент в списъка. Ако елементът присъства в списъка, тогава процесът се нарича успешен и процесът връща местоположението на този елемент. В противен случай търсенето се нарича неуспешно.
Линейното търсене и двоичното търсене са двете популярни техники за търсене. Тук ще обсъдим алгоритъма за двоично търсене.
Двоичното търсене е техниката за търсене, която работи ефективно върху сортирани списъци. Следователно, за да търсим елемент в някакъв списък, използвайки техниката на двоично търсене, трябва да сме сигурни, че списъкът е сортиран.
Двоичното търсене следва подхода „разделяй и владей“, при който списъкът е разделен на две половини и елементът се сравнява със средния елемент на списъка. Ако съвпадението бъде намерено, местоположението на средния елемент се връща. В противен случай ние търсим във всяка от половините в зависимост от резултата, получен от мача.
ЗАБЕЛЕЖКА: Двоично търсене може да се приложи върху сортирани елементи от масив. Ако елементите на списъка не са подредени по сортиран начин, първо трябва да ги сортираме.
Сега нека видим алгоритъма на двоичното търсене.
Алгоритъм
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
Работа на двоично търсене
Сега нека видим работата на алгоритъма за двоично търсене.
За да разберем работата на алгоритъма за двоично търсене, нека вземем сортиран масив. Ще бъде лесно да разберете работата на двоичното търсене с пример.
масив, сортиран в java
Има два метода за прилагане на алгоритъма за двоично търсене -
- Итеративен метод
- Рекурсивен метод
Рекурсивният метод на двоично търсене следва подхода „разделяй и владей“.
Нека елементите на масива са -
Нека елементът за търсене е, К = 56
Трябва да използваме формулата по-долу, за да изчислим средата от масива -
mid = (beg + end)/2
И така, в дадения масив -
помолвам = 0
край = 8
средата = (0 + 8)/2 = 4. И така, 4 е средата на масива.
Сега елементът за търсене е намерен. Така че алгоритъмът ще върне индекса на съвпадащия елемент.
Сложност на двоично търсене
Сега нека видим времевата сложност на двоичното търсене в най-добрия случай, средния случай и най-лошия случай. Ще видим и пространствената сложност на двоичното търсене.
1. Времева сложност
| Случай | Времева сложност |
|---|---|
| Най-добър случай | О(1) |
| Среден случай | O(вход) |
| Най-лошия случай | O(вход) |
2. Космическа сложност
| Космическа сложност | О(1) |
- Пространствената сложност на двоичното търсене е O(1).
Внедряване на двоично търсене
Сега нека видим програмите за двоично търсене на различни езици за програмиране.
програма за наследяване в python
програма: Напишете програма за прилагане на двоично търсене на език 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)> Изход
И така, това е всичко за статията. Надяваме се, че статията ще ви бъде полезна и информативна.