Vom discuta despre căutarea binară în limbajul de programare C++. Căutarea binară este un mecanism folosit pentru a găsi elementele date din matricea sortată prin înjumătățirea continuă a matricei și apoi căutarea elementelor specificate dintr-o matrice pe jumătate. Și procesul continuă până când se găsește potrivirea. Funcționează numai structurile de date sortate. Complexitatea temporală a algoritmului de căutare binar este O (log n).
Notă: Pentru a efectua o tehnică de căutare binară în C++, un programator sau utilizator trebuie să se asigure că matricea dată trebuie sortată fie în ordine crescătoare, fie în ordine descrescătoare.
Algoritmul căutării binare în C++
Urmează algoritmul pentru a efectua căutarea binară în 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'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)> Exemplul 2: Program pentru a efectua căutarea binară folosind funcția definită de utilizator
/* 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></=> În programul de mai sus, am declarat o matrice arr[] = {5, 10, 15, 20, 25, 30, 35, 40); și apoi am specificat numărul „25” la care căutați din matricea sortată folosind metoda de căutare binară. Prin urmare, creăm o funcție definită de utilizator bin_search() care caută numărul dat și returnează instrucțiunea „Elementul este găsit la poziția 5”. Dacă numărul nu este definit în matrice, funcția bin_search() arată „Elementul nu este găsit în matrice”.
Exemplul 3: Program pentru a găsi elementul specificat folosind funcția de recursivitate
Să creăm un exemplu pentru a verifica dacă elementul specificat este găsit în matricea sortată folosind căutarea binară în cadrul funcției de recursivitate.
/* 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)> În programul de mai sus, introducem toate elementele unui tablou în ordine crescătoare și apoi definim un număr, deoarece elementul țintă este „12”, care este căutat dintr-o matrice sortată folosind metoda de căutare binară. Deci, creăm o funcție definită de utilizator binary_search() care caută poziția elementului definit dintr-o matrice și returnează elementul particular disponibil în această poziție. Și dacă elementul nu este disponibil în tabloul sortat, returnează 0.