logo

Двоично търсене в C++

Ще обсъдим двоичното търсене в езика за програмиране C++. Двоичното търсене е механизъм, използван за намиране на дадени елементи от сортирания масив чрез непрекъснато разполовяване на масива и след това търсене на определени елементи от половин масив. И процесът продължава, докато се намери съвпадението. Работи само със сортираните структури от данни. Времевата сложност на алгоритъма за двоично търсене е O (log n).

Двоично търсене в C++

Забележка: За да изпълни техника за двоично търсене в C++, програмист или потребител трябва да се увери, че даденият масив трябва да бъде сортиран или във възходящ, или в низходящ ред.

Алгоритъм за двоично търсене в C++

Следва алгоритъмът за извършване на двоично търсене в C++

 beg = 0; end = size - 1; while ( beg num) { End = mid - 1; } Else if (arr [mid] <num) { beg="mid" + 1; } if the element does not exist in array, return -1. -1; < pre> <h3>Steps to perform the binary search in C++</h3> <p> <strong>Step 1:</strong> Declare the variables and input all elements of an array in sorted order (ascending or descending).</p> <p> <strong>Step 2:</strong> Divide the lists of array elements into halves.</p> <p> <strong>Step 3:</strong> Now compare the target elements with the middle element of the array. And if the value of the target element is matched with the middle element, return the middle element&apos;s position and end the search process.</p> <p> <strong>Step 4:</strong> If the target element is less than the middle element, we search the elements into the lower half of an array.</p> <p> <strong>Step 5:</strong> If the target element is larger than the middle element, we need to search the element into the greater half of the array.</p> <p> <strong>Step 6:</strong> We will continuously repeat steps 4, 5, and 6 till the specified element is not found in the sorted array.</p> <p> <strong>Example 1: Program to find the specified number from the sorted array using the binary search</strong> </p> <p>Let&apos;s write a program to find the specified number from a sorted array using the binary search in the C++ programming language.</p> <pre> #include #include using namespace std; int main () { // declaration of the variables and array int arr[100], st, mid, end, i, num, tgt; cout &lt;&lt; &apos; Define the size of the array: &apos; &lt;&gt; num; // get size // enter only sorted array cout &lt;&lt; &apos; Enter the values in sorted array either ascending or descending order: &apos; &lt;&lt; endl; // use for loop to iterate values for (i = 0; i &lt; num; i++) { cout &lt;&lt; &apos; arr [&apos; &lt;&lt; i &lt;&gt; arr[i]; } // initialize the starting and ending variable&apos;s values st = 0; end = num - 1; // size of array (num) - 1 // define the item or value to be search cout &lt;&lt; &apos; Define a value to be searched from sorted array: &apos; &lt;&gt; tgt; // use while loop to check &apos;st&apos;, should be less than equal to &apos;end&apos;. while ( st <= end) { get middle value by splitting into half mid="(" st + end ) 2; * if we the target at index, print position and exit from program. (arr[mid]="=" tgt) cout << ' element is found index < arr[mid]) 1; set new for variable } check of less than element' else ( tgt - number not found. endl; return 0; pre> <p> <strong>Output</strong> </p> <pre> Define the size of the array: 10 Enter the values in sorted array either ascending or descending order: Arr [0] = 12 Arr [1] = 24 Arr [2] = 36 Arr [3] = 48 Arr [4] = 50 Arr [5] = 54 Arr [6] = 58 Arr [7] = 60 Arr [8] = 72 Arr [9] = 84 Define a value to be searched from sorted array: 50 Element is found at index 5 </pre> <p> <strong>Example 2: Program to perform the binary search using the user-defined function</strong> </p> <pre> /* program to find the specified element from the sorted array using the binary search in C++. */ #include using namespace std; /* create user-defined function and pass different parameters: arr[] - it represents the sorted array; num variable represents the size of an array; tgt variable represents the target or specified variable to be searched in the sorted array. */ int bin_search (int arr[], int num, int tgt) { int beg = 0, end = num - 1; // use loop to check all sorted elements while (beg <= end) { * get the mid value of sorted array and then compares with target element. int + 2; if (tgt="=" arr[mid]) return mid; when is equal to tgt } check less than value, discard left element else < end="mid" - 1; greater all elements beg="mid" -1 not exists in -1; main () declaration arrays arr[]="{" 5, 10, 15, 20, 25, 30, 37, 40}; specified num="sizeof" (arr) sizeof (arr[0]); declare pos variable position (arr, num, tgt); (pos !="1)" cout << ' found at 1)<< endl; array' 0; pre> <p> <strong>Output</strong> </p> <pre> Element is found at position 5 </pre> <p>In the above program, we declared an array arr[] = {5, 10, 15, 20, 25, 30, 35, 40); and then we specified number &apos;25&apos; to which search from the sorted array using the binary search method. Therefore, we create a user-defined function bin_search() that searches the given number and returns the statement &apos;Element is found at position 5&apos;. If the number is not defined in the array, the bin_search() function shows &apos; Element is not found in the array.&apos; </p> <p> <strong>Example 3: Program to find the specified element using the recursion function</strong> </p> <p>Let&apos;s create an example to check whether the specified element is found in the sorted array using the binary search inside the recursion function.</p> <pre> /* find the specified number using the binary search technique inside the recursion method. */ #include using namespace std; // define a function int binary_search (int [], int, int, int); int main () { // declaration of the variables int i, arr[100], tgt, num, ind, st, end; cout &lt;&gt; num; cout &lt;&lt; &apos; Enter &apos; &lt;&lt; num &lt;&lt; &apos; elements in ascending order: &apos; &lt;&lt; endl; // use for loop to ieterate the number for ( i = 0; i &lt; num; i++) { cout &lt;&lt; &apos; arr [&apos; &lt;&lt; i &lt;&gt; arr[i]; } // define the element to be search cout &lt;&gt; tgt; // ind define the index number ind = binary_search (arr, 0, num - 1, tgt); // check for existemce of the specified element if (ind == 0) cout &lt;&lt; tgt &lt;&lt; &apos; is not available in the array-list&apos;; else cout &lt;&lt; tgt &lt;&lt; &apos; is available at position &apos; &lt;&lt; ind &lt; end) { return 0; } mid = (st + end) / 2; // get middle value of the sorted array // check middle value is equal to target number if (arr[mid] == tgt) { return (mid + 1); } // check mid is greater than target number else if (arr[mid]&gt; tgt) { binary_search (arr, st, mid - 1, tgt); } // check mid is less than target number else if (arr [mid] <tgt) { binary_search (arr, mid + 1, end, tgt); } < pre> <p> <strong>Output</strong> </p> <pre> Define the size of an array: 10 Arr [0] = 2 Arr [1] = 4 Arr [2] = 5 Arr [3] = 8 Arr [4] = 12 Arr [5] = 13 Arr [6] = 27 Arr [7] = 36 Arr [8] = 49 Arr [9] = 51 Enter an element to be searched in ascending array: 12 12 is available at position 6. </pre> <p>In the above program, we input all elements of an array in ascending order and then define a number as the target element is &apos;12&apos;, which is searched from a sorted array using the binary search method. So, we create a user-defined function binary_search() that searches the defined element&apos;s position from an array and returns the particular element available at this position. And if the element is not available in the sorted array, it returns 0. </p> <hr></tgt)></pre></=></pre></=></pre></num)>

Пример 2: Програма за извършване на двоично търсене с помощта на дефинирана от потребителя функция

 /* program to find the specified element from the sorted array using the binary search in C++. */ #include using namespace std; /* create user-defined function and pass different parameters: arr[] - it represents the sorted array; num variable represents the size of an array; tgt variable represents the target or specified variable to be searched in the sorted array. */ int bin_search (int arr[], int num, int tgt) { int beg = 0, end = num - 1; // use loop to check all sorted elements while (beg <= end) { * get the mid value of sorted array and then compares with target element. int + 2; if (tgt="=" arr[mid]) return mid; when is equal to tgt } check less than value, discard left element else < end="mid" - 1; greater all elements beg="mid" -1 not exists in -1; main () declaration arrays arr[]="{" 5, 10, 15, 20, 25, 30, 37, 40}; specified num="sizeof" (arr) sizeof (arr[0]); declare pos variable position (arr, num, tgt); (pos !="1)" cout << \' found at 1)<< endl; array\' 0; pre> <p> <strong>Output</strong> </p> <pre> Element is found at position 5 </pre> <p>In the above program, we declared an array arr[] = {5, 10, 15, 20, 25, 30, 35, 40); and then we specified number &apos;25&apos; to which search from the sorted array using the binary search method. Therefore, we create a user-defined function bin_search() that searches the given number and returns the statement &apos;Element is found at position 5&apos;. If the number is not defined in the array, the bin_search() function shows &apos; Element is not found in the array.&apos; </p> <p> <strong>Example 3: Program to find the specified element using the recursion function</strong> </p> <p>Let&apos;s create an example to check whether the specified element is found in the sorted array using the binary search inside the recursion function.</p> <pre> /* find the specified number using the binary search technique inside the recursion method. */ #include using namespace std; // define a function int binary_search (int [], int, int, int); int main () { // declaration of the variables int i, arr[100], tgt, num, ind, st, end; cout &lt;&gt; num; cout &lt;&lt; &apos; Enter &apos; &lt;&lt; num &lt;&lt; &apos; elements in ascending order: &apos; &lt;&lt; endl; // use for loop to ieterate the number for ( i = 0; i &lt; num; i++) { cout &lt;&lt; &apos; arr [&apos; &lt;&lt; i &lt;&gt; arr[i]; } // define the element to be search cout &lt;&gt; tgt; // ind define the index number ind = binary_search (arr, 0, num - 1, tgt); // check for existemce of the specified element if (ind == 0) cout &lt;&lt; tgt &lt;&lt; &apos; is not available in the array-list&apos;; else cout &lt;&lt; tgt &lt;&lt; &apos; is available at position &apos; &lt;&lt; ind &lt; end) { return 0; } mid = (st + end) / 2; // get middle value of the sorted array // check middle value is equal to target number if (arr[mid] == tgt) { return (mid + 1); } // check mid is greater than target number else if (arr[mid]&gt; tgt) { binary_search (arr, st, mid - 1, tgt); } // check mid is less than target number else if (arr [mid] <tgt) { binary_search (arr, mid + 1, end, tgt); } < pre> <p> <strong>Output</strong> </p> <pre> Define the size of an array: 10 Arr [0] = 2 Arr [1] = 4 Arr [2] = 5 Arr [3] = 8 Arr [4] = 12 Arr [5] = 13 Arr [6] = 27 Arr [7] = 36 Arr [8] = 49 Arr [9] = 51 Enter an element to be searched in ascending array: 12 12 is available at position 6. </pre> <p>In the above program, we input all elements of an array in ascending order and then define a number as the target element is &apos;12&apos;, which is searched from a sorted array using the binary search method. So, we create a user-defined function binary_search() that searches the defined element&apos;s position from an array and returns the particular element available at this position. And if the element is not available in the sorted array, it returns 0. </p> <hr></tgt)></pre></=>

В горната програма декларирахме масив arr[] = {5, 10, 15, 20, 25, 30, 35, 40); и след това посочихме номер '25', към който се търси от сортирания масив, използвайки метода за двоично търсене. Затова създаваме дефинирана от потребителя функция bin_search(), която търси дадения номер и връща израза „Елементът е намерен на позиция 5“. Ако числото не е дефинирано в масива, функцията bin_search() показва „Елементът не е намерен в масива“.

Пример 3: Програма за намиране на посочения елемент с помощта на функцията за рекурсия

Нека създадем пример, за да проверим дали посоченият елемент е намерен в сортирания масив, като използваме двоичното търсене във функцията за рекурсия.

 /* find the specified number using the binary search technique inside the recursion method. */ #include using namespace std; // define a function int binary_search (int [], int, int, int); int main () { // declaration of the variables int i, arr[100], tgt, num, ind, st, end; cout &lt;&gt; num; cout &lt;&lt; &apos; Enter &apos; &lt;&lt; num &lt;&lt; &apos; elements in ascending order: &apos; &lt;&lt; endl; // use for loop to ieterate the number for ( i = 0; i &lt; num; i++) { cout &lt;&lt; &apos; arr [&apos; &lt;&lt; i &lt;&gt; arr[i]; } // define the element to be search cout &lt;&gt; tgt; // ind define the index number ind = binary_search (arr, 0, num - 1, tgt); // check for existemce of the specified element if (ind == 0) cout &lt;&lt; tgt &lt;&lt; &apos; is not available in the array-list&apos;; else cout &lt;&lt; tgt &lt;&lt; &apos; is available at position &apos; &lt;&lt; ind &lt; end) { return 0; } mid = (st + end) / 2; // get middle value of the sorted array // check middle value is equal to target number if (arr[mid] == tgt) { return (mid + 1); } // check mid is greater than target number else if (arr[mid]&gt; tgt) { binary_search (arr, st, mid - 1, tgt); } // check mid is less than target number else if (arr [mid] <tgt) { binary_search (arr, mid + 1, end, tgt); } < pre> <p> <strong>Output</strong> </p> <pre> Define the size of an array: 10 Arr [0] = 2 Arr [1] = 4 Arr [2] = 5 Arr [3] = 8 Arr [4] = 12 Arr [5] = 13 Arr [6] = 27 Arr [7] = 36 Arr [8] = 49 Arr [9] = 51 Enter an element to be searched in ascending array: 12 12 is available at position 6. </pre> <p>In the above program, we input all elements of an array in ascending order and then define a number as the target element is &apos;12&apos;, which is searched from a sorted array using the binary search method. So, we create a user-defined function binary_search() that searches the defined element&apos;s position from an array and returns the particular element available at this position. And if the element is not available in the sorted array, it returns 0. </p> <hr></tgt)>

В горната програма въвеждаме всички елементи на масив във възходящ ред и след това дефинираме число като целевият елемент е „12“, който се търси от сортиран масив с помощта на метода за двоично търсене. И така, създаваме дефинирана от потребителя функция binary_search(), която търси позицията на дефинирания елемент от масив и връща конкретния елемент, наличен на тази позиция. И ако елементът не е наличен в сортирания масив, той връща 0.