We bespreken het binair zoeken in de programmeertaal C++. Binair zoeken is een mechanisme dat wordt gebruikt om de gegeven elementen uit de gesorteerde array te vinden door de array continu te halveren en vervolgens naar specifieke elementen uit een halve array te zoeken. En het proces gaat door totdat de match is gevonden. Het werkt alleen met de gesorteerde datastructuren. De tijdscomplexiteit van het binaire zoekalgoritme is O (log n).
Opmerking: Om een binaire zoektechniek in C++ uit te voeren, moet een programmeur of gebruiker ervoor zorgen dat de gegeven array in oplopende of aflopende volgorde wordt gesorteerd.
Algoritme van de binaire zoekopdracht in C++
Hieronder volgt het algoritme om de binaire zoekopdracht in C++ uit te voeren
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'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'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 << ' Define the size of the array: ' <> num; // get size // enter only sorted array cout << ' Enter the values in sorted array either ascending or descending order: ' << endl; // use for loop to iterate values for (i = 0; i < num; i++) { cout << ' arr [' << i <> arr[i]; } // initialize the starting and ending variable's values st = 0; end = num - 1; // size of array (num) - 1 // define the item or value to be search cout << ' Define a value to be searched from sorted array: ' <> tgt; // use while loop to check 'st', should be less than equal to 'end'. 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 '25' 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 'Element is found at position 5'. If the number is not defined in the array, the bin_search() function shows ' Element is not found in the array.' </p> <p> <strong>Example 3: Program to find the specified element using the recursion function</strong> </p> <p>Let'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 <> num; cout << ' Enter ' << num << ' elements in ascending order: ' << endl; // use for loop to ieterate the number for ( i = 0; i < num; i++) { cout << ' arr [' << i <> arr[i]; } // define the element to be search cout <> 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 << tgt << ' is not available in the array-list'; else cout << tgt << ' is available at position ' << ind < 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]> 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 '12', 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'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)> Voorbeeld 2: Programma om de binaire zoekopdracht uit te voeren met behulp van de door de gebruiker gedefinieerde functie
/* 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 '25' 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 'Element is found at position 5'. If the number is not defined in the array, the bin_search() function shows ' Element is not found in the array.' </p> <p> <strong>Example 3: Program to find the specified element using the recursion function</strong> </p> <p>Let'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 <> num; cout << ' Enter ' << num << ' elements in ascending order: ' << endl; // use for loop to ieterate the number for ( i = 0; i < num; i++) { cout << ' arr [' << i <> arr[i]; } // define the element to be search cout <> 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 << tgt << ' is not available in the array-list'; else cout << tgt << ' is available at position ' << ind < 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]> 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 '12', 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'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></=> In het bovenstaande programma hebben we een array gedeclareerd arr[] = {5, 10, 15, 20, 25, 30, 35, 40); en vervolgens specificeerden we nummer '25' waarnaar gezocht werd vanuit de gesorteerde array met behulp van de binaire zoekmethode. Daarom creëren we een door de gebruiker gedefinieerde functie bin_search() die het opgegeven getal doorzoekt en de verklaring 'Element is gevonden op positie 5' retourneert. Als het getal niet in de array is gedefinieerd, toont de functie bin_search() 'Element is niet gevonden in de array.'
Voorbeeld 3: Programma om het opgegeven element te vinden met behulp van de recursiefunctie
Laten we een voorbeeld maken om te controleren of het opgegeven element in de gesorteerde array wordt gevonden met behulp van de binaire zoekopdracht binnen de recursiefunctie.
/* 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 <> num; cout << ' Enter ' << num << ' elements in ascending order: ' << endl; // use for loop to ieterate the number for ( i = 0; i < num; i++) { cout << ' arr [' << i <> arr[i]; } // define the element to be search cout <> 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 << tgt << ' is not available in the array-list'; else cout << tgt << ' is available at position ' << ind < 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]> 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 '12', 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'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)> In het bovenstaande programma voeren we alle elementen van een array in oplopende volgorde in en definiëren vervolgens een getal omdat het doelelement '12' is, dat wordt doorzocht vanuit een gesorteerde array met behulp van de binaire zoekmethode. We creëren dus een door de gebruiker gedefinieerde functie binary_search() die de positie van het gedefinieerde element uit een array doorzoekt en het specifieke element retourneert dat op deze positie beschikbaar is. En als het element niet beschikbaar is in de gesorteerde array, retourneert het 0.
mama kulkarni