Vi vil diskutere det binære søket i programmeringsspråket C++. Binært søk er en mekanisme som brukes til å finne de gitte elementene fra den sorterte matrisen ved kontinuerlig å halvere matrisen og deretter søke spesifiserte elementer fra en halv matrise. Og prosessen fortsetter til matchen er funnet. Det fungerer bare de sorterte datastrukturene. Tidskompleksiteten til den binære søkealgoritmen er O (log n).

Merk: For å utføre en binær søketeknikk i C++, bør en programmerer eller bruker sørge for at den gitte matrisen må sorteres enten i stigende eller synkende rekkefølge.

Algoritme for binærsøk i C++

Følgende er algoritmen for å utføre det binære søket i 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&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)>

Eksempel 2: Program for å utføre det binære søket ved å bruke den brukerdefinerte funksjonen

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

I programmet ovenfor erklærte vi en matrise arr[] = {5, 10, 15, 20, 25, 30, 35, 40); og så spesifiserte vi nummer '25' som søker fra den sorterte matrisen ved å bruke den binære søkemetoden. Derfor lager vi en brukerdefinert funksjon bin_search() som søker etter det gitte tallet og returnerer setningen 'Element er funnet på posisjon 5'. Hvis tallet ikke er definert i matrisen, viser bin_search()-funksjonen 'Elementet er ikke funnet i matrisen.'

Eksempel 3: Program for å finne det angitte elementet ved hjelp av rekursjonsfunksjonen

La oss lage et eksempel for å sjekke om det angitte elementet finnes i den sorterte matrisen ved å bruke det binære søket inne i rekursjonsfunksjonen.

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

I programmet ovenfor legger vi inn alle elementene i en matrise i stigende rekkefølge og definerer deretter et tall ettersom målelementet er '12', som søkes fra en sortert matrise ved hjelp av den binære søkemetoden. Så vi lager en brukerdefinert funksjon binary_search() som søker etter det definerte elementets posisjon fra en matrise og returnerer det spesielle elementet som er tilgjengelig på denne posisjonen. Og hvis elementet ikke er tilgjengelig i den sorterte matrisen, returnerer det 0.