Keskustelemme binäärihausta C++-ohjelmointikielellä. Binäärihaku on mekanismi, jolla löydetään annetut elementit lajitetusta taulukosta puolittamalla taulukko jatkuvasti ja etsimällä sitten tiettyjä elementtejä puolikkaasta taulukosta. Ja prosessi jatkuu, kunnes ottelu löytyy. Se toimii vain lajiteltuja tietorakenteita. Binaarihakualgoritmin aikamonimutkaisuus on O (log n).
Huomautus: Binäärihakutekniikan suorittamiseksi C++:ssa ohjelmoijan tai käyttäjän tulee varmistaa, että annettu matriisi on lajiteltava joko nousevaan tai laskevaan järjestykseen.
Binäärihaun algoritmi C++:ssa
Seuraavassa on algoritmi binäärihaun suorittamiseksi C++:ssa
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)> Esimerkki 2: Ohjelma suorittaa binäärihaun käyttämällä käyttäjän määrittämää toimintoa
voi abstraktilla luokalla olla rakentaja
/* 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></=> Yllä olevassa ohjelmassa julistimme taulukon arr[] = {5, 10, 15, 20, 25, 30, 35, 40); ja sitten määritimme luvun '25', johon haetaan lajiteltua taulukkoa käyttämällä binäärihakumenetelmää. Siksi luomme käyttäjän määrittämän funktion bin_search(), joka etsii annetusta numerosta ja palauttaa lauseen 'Elementti löytyy paikasta 5'. Jos numeroa ei ole määritetty taulukossa, bin_search()-funktio näyttää 'Elementtiä ei löydy taulukosta.'
jfx java opetusohjelma
Esimerkki 3: Ohjelmoi määritetyn elementin etsiminen rekursiofunktiolla
Luodaan esimerkki tarkistaaksesi löytyykö määritetty elementti lajitetusta taulukosta käyttämällä binäärihakua rekursiofunktion sisällä.
/* 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)> Yllä olevassa ohjelmassa syötetään kaikki taulukon elementit nousevassa järjestyksessä ja määritetään sitten numero, koska kohdeelementti on '12', joka etsitään lajitetusta taulukosta binäärihakumenetelmällä. Joten luomme käyttäjän määrittämän funktion binary_search(), joka etsii määritellyn elementin sijainnin taulukosta ja palauttaa tietyn tässä paikassa käytettävissä olevan elementin. Ja jos elementti ei ole käytettävissä lajitetussa taulukossa, se palauttaa arvon 0.