في هذه المقالة، سنناقش خوارزمية البحث الثنائي. البحث هو عملية العثور على عنصر معين في القائمة. إذا كان العنصر موجودًا في القائمة، فسيتم تسمية العملية بأنها ناجحة، وتقوم العملية بإرجاع موقع هذا العنصر. خلاف ذلك، يسمى البحث غير ناجح.
يعد البحث الخطي والبحث الثنائي من تقنيات البحث الشائعة. سنناقش هنا خوارزمية البحث الثنائي.
البحث الثنائي هو أسلوب بحث يعمل بكفاءة على القوائم المصنفة. وبالتالي، للبحث عن عنصر في قائمة ما باستخدام تقنية البحث الثنائي، يجب علينا التأكد من فرز القائمة.
يتبع البحث الثنائي أسلوب فرق تسد حيث يتم تقسيم القائمة إلى نصفين، ويتم مقارنة العنصر بالعنصر الأوسط في القائمة. إذا تم العثور على التطابق، فسيتم إرجاع موقع العنصر الأوسط. بخلاف ذلك، فإننا نبحث في أي من الشوطين اعتمادًا على النتيجة التي تم الحصول عليها خلال المباراة.
ملاحظة: يمكن تنفيذ البحث الثنائي على عناصر الصفيف التي تم فرزها. إذا لم يتم ترتيب عناصر القائمة بطريقة مرتبة، فيجب علينا فرزها أولاً.
الآن، دعونا نرى خوارزمية البحث الثنائي.
خوارزمية
Binary_Search(a, lower_bound, upper_bound, val) // 'a' is the given array, 'lower_bound' is the index of the first array element, 'upper_bound' is the index of the last array element, 'val' is the value to search Step 1: set beg = lower_bound, end = upper_bound, pos = - 1 Step 2: repeat steps 3 and 4 while beg val set end = mid - 1 else set beg = mid + 1 [end of if] [end of loop] Step 5: if pos = -1 print 'value is not present in the array' [end of if] Step 6: exit
عمل البحث الثنائي
الآن، دعونا نرى عمل خوارزمية البحث الثنائي.
لفهم عمل خوارزمية البحث الثنائي، لنأخذ مصفوفة مرتبة. سيكون من السهل فهم آلية عمل البحث الثنائي من خلال مثال.
هناك طريقتان لتنفيذ خوارزمية البحث الثنائي -
- طريقة تكرارية
- طريقة العودية
تتبع الطريقة العودية للبحث الثنائي نهج فرق تسد.
دع عناصر المصفوفة هي -
دع العنصر للبحث هو ، ك = 56
يتعين علينا استخدام الصيغة أدناه لحساب منتصف من المصفوفة -
mid = (beg + end)/2
لذلك، في المصفوفة المحددة -
إفترض جدلا = 0
نهاية = 8
منتصف = (0 + 8)/2 = 4. إذن، 4 هو منتصف المصفوفة.
الآن تم العثور على العنصر المراد البحث عنه. لذلك ستعيد الخوارزمية فهرس العنصر المطابق.
تعقيد البحث الثنائي
الآن، دعونا نرى التعقيد الزمني للبحث الثنائي في أفضل حالة، ومتوسطة، وأسوأ حالة. سنرى أيضًا مدى تعقيد مساحة البحث الثنائي.
1. تعقيد الوقت
| قضية | تعقيد الوقت |
|---|---|
| أفضل حالة | يا(1) |
| متوسط الحالة | يا (تسجيل الدخول) |
| الحالة الأسوأ | يا (تسجيل الدخول) |
2. تعقيد الفضاء
| تعقيد الفضاء | يا(1) |
- التعقيد المكاني للبحث الثنائي هو O(1).
تنفيذ البحث الثنائي
والآن دعونا نتعرف على برامج البحث الثنائي بلغات البرمجة المختلفة.
برنامج: كتابة برنامج لتنفيذ البحث الثنائي بلغة C.
#include int binarySearch(int a[], int beg, int end, int val) { int mid; if(end >= beg) { mid = (beg + end)/2; /* if the item to be searched is present at middle */ if(a[mid] == val) { return mid+1; } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if(a[mid] <val) { return binarysearch(a, mid+1, end, val); } * if the item to be searched is greater than middle, then it can only in right subarray else beg, mid-1, -1; int main() a[]="{11," 14, 25, 30, 40, 41, 52, 57, 70}; given array val="40;" value n="sizeof(a)" sizeof(a[0]); size of res="binarySearch(a," 0, n-1, store result printf('the elements are - '); for (int i="0;" < n; i++) printf('%d ', a[i]); printf('
element %d', (res="=" -1) not present array'); at %d position array', res); 0; pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-5.webp" alt="Binary Search Algorithm"> <p> <strong>Program:</strong> Write a program to implement Binary search in C++.</p> <pre> #include using namespace std; int binarySearch(int a[], int beg, int end, int val) { int mid; if(end >= beg) { mid = (beg + end)/2; /* if the item to be searched is present at middle */ if(a[mid] == val) { return mid+1; } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if(a[mid] <val) { return binarysearch(a, mid+1, end, val); } * if the item to be searched is greater than middle, then it can only in right subarray else beg, mid-1, -1; int main() a[]="{10," 12, 24, 29, 39, 40, 51, 56, 70}; given array val="51;" value n="sizeof(a)" sizeof(a[0]); size of res="binarySearch(a," 0, n-1, store result cout<<'the elements are - '; for (int i="0;" < n; i++) cout< <a[i]<<' cout<<'
element '<<val; (res="=" -1) not present array'; at '<<res<<' position 0; pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-6.webp" alt="Binary Search Algorithm"> <p> <strong>Program:</strong> Write a program to implement Binary search in C#.</p> <pre> using System; class BinarySearch { static int binarySearch(int[] a, int beg, int end, int val) { int mid; if(end >= beg) { mid = (beg + end)/2; if(a[mid] == val) { return mid+1; /* if the item to be searched is present at middle */ } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if(a[mid] <val) { return binarysearch(a, mid+1, end, val); } * if the item to be searched is greater than middle, then it can only in right subarray else beg, mid-1, -1; static void main() int[] a="{9," 11, 23, 28, 38, 45, 50, 56, 70}; given array int val="70;" value n="a.Length;" size of res="binarySearch(a," 0, n-1, store result console.write('the elements are - '); for (int i="0;" < n; i++) console.write(a[i] + ' console.writeline(); console.writeline('element (res="=" -1) not present array'); at position pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-7.webp" alt="Binary Search Algorithm"> <p> <strong>Program:</strong> Write a program to implement Binary search in Java.</p> <pre> class BinarySearch { static int binarySearch(int a[], int beg, int end, int val) { int mid; if(end >= beg) { mid = (beg + end)/2; if(a[mid] == val) { return mid+1; /* if the item to be searched is present at middle */ } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if(a[mid] <val) { return binarysearch(a, mid+1, end, val); } * if the item to be searched is greater than middle, then it can only in right subarray else beg, mid-1, -1; public static void main(string args[]) int a[]="{8," 10, 22, 27, 37, 44, 49, 55, 69}; given array val="37;" value n="a.length;" size of res="binarySearch(a," 0, n-1, store result system.out.print('the elements are: '); for (int i="0;" < n; i++) system.out.print(a[i] + ' system.out.println(); system.out.println('element is: (res="=" -1) not present array'); at position pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-8.webp" alt="Binary Search Algorithm"> <p> <strong>Program:</strong> Write a program to implement Binary search in PHP.</p> <pre> = $beg) { $mid = floor(($beg + $end)/2); if($a[$mid] == $val) { return $mid+1; /* if the item to be searched is present at middle */ } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if($a[$mid] <$val) { return binarysearch($a, $mid+1, $end, $val); } * if the item to be searched is greater than middle, then it can only in right subarray else $beg, $mid-1, -1; $a="array(7," 9, 21, 26, 36, 43, 48, 54, 68); given array $val="68;" value $n="sizeof($a);" size of $res="binarySearch($a," 0, $n-1, store result echo 'the elements are: '; for ($i="0;" $i < $n; $i++) ' , $a[$i]; <br>' , 'Element to be searched is: ' , $val; if ($res == -1) echo ' <br>' , 'Element is not present in the array'; else echo ' <br>' , 'Element is present at ' , $res , ' position of array'; ?> </$val)></pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-9.webp" alt="Binary Search Algorithm"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></val)></pre></val)></pre></val)></pre></val)> انتاج |
لذلك، هذا كل ما في هذه المادة. نأمل أن تكون المقالة مفيدة وغنية بالمعلومات لك.