سنناقش البحث الثنائي في لغة البرمجة C++. البحث الثنائي هو آلية تستخدم للعثور على العناصر المحددة من المصفوفة التي تم فرزها عن طريق خفض المصفوفة إلى النصف بشكل مستمر ثم البحث عن العناصر المحددة من مصفوفة نصفية. وتستمر العملية حتى يتم العثور على المباراة. إنه يعمل فقط على هياكل البيانات التي تم فرزها. التعقيد الزمني لخوارزمية البحث الثنائي هو O (log n).
دمج النوع
ملاحظة: لإجراء تقنية بحث ثنائي في لغة C++، يجب على المبرمج أو المستخدم التأكد من ضرورة فرز المصفوفة المحددة إما بترتيب تصاعدي أو تنازلي.
خوارزمية البحث الثنائي في لغة C++
فيما يلي الخوارزمية لإجراء البحث الثنائي في 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)> مثال 2: برنامج لإجراء البحث الثنائي باستخدام الوظيفة المحددة من قبل المستخدم
/* 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></=> في البرنامج أعلاه، أعلنا عن مصفوفة arr[] = {5, 10, 15, 20, 25, 30, 35, 40); ومن ثم قمنا بتحديد الرقم '25' الذي سيتم البحث عنه من المصفوفة المصنفة باستخدام طريقة البحث الثنائي. لذلك، نقوم بإنشاء دالة محددة من قبل المستخدم bin_search() والتي تبحث في الرقم المحدد وترجع العبارة 'تم العثور على العنصر في الموضع 5'. إذا لم يتم تعريف الرقم في المصفوفة، فستعرض الدالة bin_search() 'العنصر غير موجود في المصفوفة'.
مثال 3: برنامج للعثور على العنصر المحدد باستخدام وظيفة العودية
فرق تاريخ التفوق
لنقم بإنشاء مثال للتحقق مما إذا كان العنصر المحدد موجودًا في المصفوفة التي تم فرزها باستخدام البحث الثنائي داخل وظيفة العودية.
/* 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)> في البرنامج أعلاه، نقوم بإدخال جميع عناصر المصفوفة بترتيب تصاعدي ثم نحدد رقمًا حيث أن العنصر الهدف هو '12'، والذي يتم البحث عنه من مصفوفة مرتبة باستخدام طريقة البحث الثنائي. لذلك، نقوم بإنشاء دالة معرفة من قبل المستخدم ثنائي_البحث() الذي يبحث في موضع العنصر المحدد من مصفوفة ويعيد العنصر المحدد المتاح في هذا الموضع. وإذا كان العنصر غير متوفر في المصفوفة التي تم فرزها، فإنه يُرجع 0.