الطريقة السريعة لتحديد موقع عنصر معين في مصفوفة مرتبة هي البحث الثنائي. المهمة الأولية لهذه الخوارزمية هي مقارنة القيمة المستهدفة بالعنصر الأوسط للمصفوفة. يعتبر البحث ناجحا إذا كانت القيمة المستهدفة موجودة في العنصر الأوسط. ستبحث الخوارزمية في النصف الأيسر من المصفوفة إذا كانت قيمة الهدف أقل من العنصر الأوسط. سيقوم البرنامج بمسح النصف الأيمن من المصفوفة إذا كانت قيمة الهدف أكبر من العنصر الأوسط. يتم تكرار هذه الطريقة حتى يتم استنفاد قيمة الهدف أو نطاق البحث.
كيفية قراءة ملف json
الاستخدام:
قواعد البيانات ومحركات البحث ومعالجة البيانات ليست سوى عدد قليل من التطبيقات التي تستخدم استراتيجية البحث الثنائي.
صفات:
- يجب فرز مجموعة قيم الإدخال.
- مع كل تكرار، تعمل الطريقة على تقليص نطاق البحث إلى النصف، مما يجعلها فعالة بشكل خاص لمجموعات البيانات الضخمة.
- تحتوي الخوارزمية على تعقيد زمني لأسوأ حالة O (log n).
- يتم العثور على القيمة المطلوبة بواسطة البرنامج باستخدام استراتيجية فرق تسد.
فيما يلي مثال مباشر لخوارزمية البحث الثنائية المكتوبة بلغة C:
#include int binary_search(int arr[], int left, int right, int target) { while (left <= right) { int mid="left" + (right - left) 2; if (arr[mid]="=" target) return mid; } else < left="mid" 1; right="mid" -1; target not found main() arr[]="{1," 3, 5, 7, 9}; n="sizeof(arr)" sizeof(arr[0]); index="binary_search(arr," 0, 1, target); (index="=" -1) printf('target found
'); at %d
', index); 0; pre> <p> <strong>Output:</strong> </p> <pre> Target found at index 2 </pre> <ul> <li>The binary_search function accepts four arguments: the array to search, the left and right search range boundaries, and the target value to look for. The function returns its index if the desired value can be found; else, it returns -1.</li> <li>The main function creates an array arr and a value target. The binary_search function is then used to search the array for the desired value. The function returns the index where the target value was located if it was, the function returns the index at which it was found. Otherwise, the message 'Target not found' is displayed.</li> <li>The binary search algorithm's implementation is basic. We begin by setting the left border to the array's initial index and the right boundary to the array's last index. Once the left boundary is less than or equal to the right border, the array is looped through one more time. We use the formula (left + right) / 2 within the loop to calculate the middle index of the search range. This formula computes the integer value of the middle index's floor.</li> <li>The centre member of the array is contrasted with the target value. We return the index of the middle element if they are equal. We change the right boundary to be one less than the middle index if the desired value is less than the middle element. If not, we adjust the left border so that it is one more than the centre index. We continue doing this until the goal value is obtained or the search space is filled.</li> <li>The temporal complexity of the binary search algorithm, where n is the array size, is O(log n). This is far more efficient than linear search, which has a temporal complexity of O(n), where n is the size of the array.</li> <li>Finally, the binary search technique offers a useful way to locate a particular member in a sorted array. It is easy to build and has an O(log n) time complexity, making it an efficient approach for large datasets.</li> </ul> <h3>Advantages:</h3> <ul> <li>For large datasets, the binary search algorithm is exceptionally efficient, and it is capable of handling a wide range of input sizes.</li> <li>The algorithm is simple to implement in almost all programming languages.</li> </ul> <h3>Disadvantages:</h3> <ul> <li>Before using the binary search technique, the input array must be sorted, which takes more time and memory.</li> <li>The algorithm cannot be applied to unsorted arrays.</li> <li>The algorithm may yield inaccurate results if the input array is not sorted.</li> <li>The binary search algorithm is not appropriate for tiny datasets since the technique's overhead may outweigh its benefits.</li> </ul> <h2>Conclusion:</h2> <p>A sorted array can be quickly searched for a specific element using the binary search technique. It employs a divide-and-conquer strategy to cut the search range in half with each iteration, allowing it to be highly efficient for large datasets. However, before using the binary search technique, the input array must be sorted, which takes extra time and memory. The binary search algorithm is a sophisticated data processing tool that is widely utilised in various sectors.</p> <hr></=> - تقبل وظيفة البحث الثنائي أربع وسائط: المصفوفة التي سيتم البحث عنها، وحدود نطاق البحث اليمنى واليسرى، والقيمة المستهدفة التي سيتم البحث عنها. تقوم الدالة بإرجاع فهرسها إذا كان من الممكن العثور على القيمة المطلوبة؛ وإلا فإنها ترجع -1.
- تقوم الوظيفة الرئيسية بإنشاء مصفوفة وهدف القيمة. يتم بعد ذلك استخدام وظيفة البحث الثنائي للبحث في المصفوفة عن القيمة المطلوبة. تقوم الدالة بإرجاع الفهرس الذي توجد فيه القيمة المستهدفة، إذا كانت كذلك، تقوم الدالة بإرجاع الفهرس الذي تم العثور عليها فيه. وإلا سيتم عرض الرسالة 'لم يتم العثور على الهدف'.
- يعد تنفيذ خوارزمية البحث الثنائي أمرًا أساسيًا. نبدأ بتعيين الحد الأيسر للفهرس الأولي للمصفوفة والحد الأيمن للفهرس الأخير للمصفوفة. بمجرد أن يصبح الحد الأيسر أقل من أو يساوي الحد الأيمن، يتم تكرار المصفوفة مرة أخرى. نستخدم الصيغة (يسار + يمين) / 2 داخل الحلقة لحساب المؤشر الأوسط لنطاق البحث. تحسب هذه الصيغة القيمة الصحيحة لأرضية المؤشر الأوسط.
- يتناقض العضو الأوسط للمصفوفة مع القيمة المستهدفة. نعيد فهرس العنصر الأوسط إذا كانا متساويين. نقوم بتغيير الحد الأيمن ليكون أقل من المؤشر الأوسط بواحد إذا كانت القيمة المطلوبة أقل من العنصر الأوسط. إذا لم يكن الأمر كذلك، فإننا نضبط الحد الأيسر بحيث يكون أكثر من مؤشر المركز بمقدار واحد. ونستمر بذلك حتى يتم الحصول على قيمة الهدف أو ملء مساحة البحث.
- التعقيد الزمني لخوارزمية البحث الثنائي، حيث n هو حجم المصفوفة، هو O(log n). يعد هذا أكثر كفاءة بكثير من البحث الخطي، الذي يحتوي على تعقيد زمني قدره O(n)، حيث n هو حجم المصفوفة.
- وأخيرًا، توفر تقنية البحث الثنائي طريقة مفيدة لتحديد موقع عضو معين في مصفوفة مرتبة. إنه سهل الإنشاء ويحتوي على تعقيد زمني O(log n)، مما يجعله أسلوبًا فعالاً لمجموعات البيانات الكبيرة.
مزايا:
- بالنسبة لمجموعات البيانات الكبيرة، تكون خوارزمية البحث الثنائي فعالة بشكل استثنائي، وهي قادرة على التعامل مع مجموعة واسعة من أحجام المدخلات.
- الخوارزمية سهلة التنفيذ في جميع لغات البرمجة تقريبًا.
سلبيات:
- قبل استخدام تقنية البحث الثنائي، يجب فرز مصفوفة الإدخال، الأمر الذي يستغرق المزيد من الوقت والذاكرة.
- لا يمكن تطبيق الخوارزمية على المصفوفات غير المصنفة.
- قد تسفر الخوارزمية عن نتائج غير دقيقة إذا لم يتم فرز مصفوفة الإدخال.
- خوارزمية البحث الثنائي ليست مناسبة لمجموعات البيانات الصغيرة نظرًا لأن النفقات العامة لهذه التقنية قد تفوق فوائدها.
خاتمة:
يمكن البحث بسرعة عن مصفوفة مرتبة عن عنصر محدد باستخدام تقنية البحث الثنائي. وهي تستخدم استراتيجية فرق تسد لتقليص نطاق البحث إلى النصف مع كل تكرار، مما يسمح لها بأن تكون ذات كفاءة عالية لمجموعات البيانات الكبيرة. ومع ذلك، قبل استخدام تقنية البحث الثنائي، يجب فرز مصفوفة الإدخال، الأمر الذي يستغرق وقتًا وذاكرة إضافية. تعد خوارزمية البحث الثنائي أداة معقدة لمعالجة البيانات يتم استخدامها على نطاق واسع في مختلف القطاعات.