Mēs apspriedīsim bināro meklēšanu C++ programmēšanas valodā. Binārā meklēšana ir mehānisms, ko izmanto, lai atrastu dotos elementus no sakārtotā masīva, nepārtraukti samazinot masīvu uz pusi un pēc tam meklējot norādītos elementus no pusmasīva. Un process turpinās, līdz tiek atrasta atbilstība. Tas darbojas tikai sakārtotās datu struktūras. Binārās meklēšanas algoritma laika sarežģītība ir O (log n).
Piezīme. Lai veiktu bināro meklēšanas paņēmienu programmā C++, programmētājam vai lietotājam ir jānodrošina, lai dotais masīvs būtu sakārtots augošā vai dilstošā secībā.
Binārās meklēšanas algoritms programmā C++
Tālāk ir sniegts algoritms binārās meklēšanas veikšanai C++
griešanas rīks ubuntu
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)> 2. piemērs. Programma binārās meklēšanas veikšanai, izmantojot lietotāja definētu funkciju
/* 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></=> Iepriekš minētajā programmā mēs deklarējām masīvu arr[] = {5, 10, 15, 20, 25, 30, 35, 40); un tad mēs norādījām skaitli '25', uz kuru meklēt no sakārtotā masīva, izmantojot bināro meklēšanas metodi. Tāpēc mēs izveidojam lietotāja definētu funkciju bin_search(), kas meklē norādīto numuru un atgriež paziņojumu 'Elements is found at position 5'. Ja skaitlis masīvā nav definēts, funkcija bin_search() parāda 'Elements nav atrasts masīvā.'
3. piemērs. Programma norādītā elementa atrašanai, izmantojot rekursijas funkciju
Izveidosim piemēru, lai pārbaudītu, vai norādītais elements ir atrodams sakārtotajā masīvā, izmantojot bināro meklēšanu rekursijas funkcijas iekšienē.
b plus koks
/* 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)> Iepriekš minētajā programmā mēs ievadām visus masīva elementus augošā secībā un pēc tam definējam skaitli, jo mērķa elements ir “12”, kas tiek meklēts no sakārtota masīva, izmantojot binārās meklēšanas metodi. Tātad, mēs izveidojam lietotāja definētu funkciju binary_search(), kas meklē definētā elementa pozīciju no masīva un atgriež konkrēto šajā pozīcijā pieejamo elementu. Un, ja elements nav pieejams sakārtotajā masīvā, tas atgriež 0.