logo

Bináris keresés C++ nyelven

Megbeszéljük a bináris keresést a C++ programozási nyelven. A bináris keresés egy olyan mechanizmus, amellyel az adott elemeket a rendezett tömbből úgy találjuk meg, hogy folyamatosan felezzük a tömböt, majd egy fél tömbből keresünk meghatározott elemeket. És a folyamat addig tart, amíg meg nem találják a megfelelőt. Csak a rendezett adatstruktúrákkal működik. A bináris keresési algoritmus időbonyolultsága O (log n).

Bináris keresés C++ nyelven

Megjegyzés: A bináris keresési technika C++ nyelven történő végrehajtásához a programozónak vagy felhasználónak gondoskodnia kell arról, hogy az adott tömb növekvő vagy csökkenő sorrendben legyen rendezve.

A bináris keresés algoritmusa C++ nyelven

Az alábbiakban bemutatjuk a bináris keresés végrehajtására szolgáló algoritmust C++ nyelven

 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. példa: Program a bináris keresés végrehajtására a felhasználó által definiált függvény használatával

 /* 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></=>

A fenti programban deklaráltunk egy tömböt arr[] = {5, 10, 15, 20, 25, 30, 35, 40); majd megadtuk a '25' számot, amelyre a rendezett tömbből bináris keresési módszerrel kereshet. Ezért létrehozunk egy felhasználó által definiált bin_search() függvényt, amely megkeresi a megadott számot, és az 'Elem az 5. pozícióban található' utasítást adja vissza. Ha a szám nincs megadva a tömbben, a bin_search() függvény azt mutatja, hogy 'Az elem nem található a tömbben.'

3. példa: Program a megadott elem megkeresésére a rekurziós függvény segítségével

Hozzunk létre egy példát annak ellenőrzésére, hogy a megadott elem megtalálható-e a rendezett tömbben a rekurziós függvényen belüli bináris keresés segítségével.

 /* 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)>

A fenti programban egy tömb összes elemét beírjuk növekvő sorrendben, majd megadunk egy számot, mivel a célelem '12', amelyet a rendszer egy rendezett tömbből keres a bináris keresési módszerrel. Tehát létrehozunk egy felhasználó által definiált binary_search() függvényt, amely megkeresi a definiált elem pozícióját egy tömbből, és visszaadja az adott helyen elérhető elemet. És ha az elem nem érhető el a rendezett tömbben, akkor 0-t ad vissza.