У цій статті ми обговоримо алгоритм бінарного пошуку. Пошук — це процес пошуку певного елемента в списку. Якщо елемент присутній у списку, то процес називається успішним, і процес повертає розташування цього елемента. В іншому випадку пошук вважається невдалим.
arp команда
Лінійний пошук і бінарний пошук є двома популярними методами пошуку. Тут ми обговоримо алгоритм бінарного пошуку.
Двійковий пошук — це техніка пошуку, яка ефективно працює з відсортованими списками. Отже, щоб шукати елемент у якомусь списку за допомогою техніки бінарного пошуку, ми повинні переконатися, що список відсортовано.
Двійковий пошук дотримується підходу «розділяй і володарюй», згідно з яким список ділиться на дві половини, а елемент порівнюється із середнім елементом списку. Якщо відповідність знайдено, повертається розташування середнього елемента. В іншому випадку ми шукаємо будь-який із таймів залежно від результату матчу.
ПРИМІТКА. Двійковий пошук можна реалізувати на відсортованих елементах масиву. Якщо елементи списку не впорядковано, ми повинні спочатку їх відсортувати.
Тепер розглянемо алгоритм бінарного пошуку.
Алгоритм
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
Отже, у заданому масиві -
які місяці q1
просити = 0
кінець = 8
середина = (0 + 8)/2 = 4. Отже, 4 — це середина масиву.
Тепер елемент для пошуку знайдено. Отже, алгоритм поверне індекс відповідного елемента.
Складність бінарного пошуку
Тепер давайте подивимося на часову складність двійкового пошуку в найкращому, середньому та гіршому випадку. Ми також побачимо просторову складність бінарного пошуку.
1. Складність часу
| Справа | Складність часу |
|---|---|
| Кращий випадок | O(1) |
| Середній випадок | O (вхід) |
| Найгірший випадок | O (вхід) |
2. Просторова складність
| Космічна складність | O(1) |
- Просторова складність двійкового пошуку дорівнює O(1).
Реалізація бінарного пошуку
Тепер розглянемо програми бінарного пошуку на різних мовах програмування.
програма: Напишіть програму для реалізації двійкового пошуку мовою 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)> Вихід
Отже, це все про статтю. Сподіваюся, стаття буде для вас корисною та інформативною.