كيفية العثور على رقم في صفيف: الطرق والأمثلة الأساسية

يعد العثور على رقم في مصفوفة مهمة مهمة تنشأ غالبا عند تطوير البرامج أو تحليل البيانات. بغض النظر عما إذا كانت مجموعة من الأرقام أو السلاسل أو العناصر الأكثر تعقيدا ، فقد يكون العثور على القيمة الصحيحة أمرا صعبا ويتطلب معرفة ومهارات معينة.

في هذه المقالة ، سنلقي نظرة على الطرق الأساسية للبحث عن رقم في مصفوفة ونقدم أمثلة على استخدامها. سيساعدك إتقان هذه الأساليب على التعامل مع المهام المرتبطة بالبحث عن الأرقام في صفيف بشكل أكثر كفاءة وثقة.

البحث الخطي هو نهج بسيط وبديهي للعثور على رقم في صفيف. وهو يتألف من حقيقة أننا ننظر من خلال كل عنصر من عناصر الصفيف بدوره ومقارنته بالقيمة التي نحتاج إلى العثور عليها. إذا تم العثور على قيمة مطابقة ، فإننا نعيد فهرسها في المصفوفة.

وتجدر الإشارة إلى أن البحث الخطي هو أبسط طريقة ، ولكنه قد لا يكون الأكثر فعالية ، خاصة إذا كانت المصفوفة تحتوي على عدد كبير من العناصر. في مثل هذه الحالات ، من المفيد النظر في خوارزميات أكثر تعقيدا ، مثل البحث الثنائي أو البحث في جدول التجزئة.

1. ما هو صفيف?
2. طرق البحث عن رقم في صفيف
3. طريقة البحث الخطي
4. طريقة البحث الثنائي
5. طريقة البحث الاستيفاء
6. طرق البحث باستخدام الوظائف القياسية
7. البحث عن الرقم الخطي
8. البحث عن رقم ثنائي
9. البحث عن رقم الاستيفاء
10. جداول التجزئة للبحث عن رقم
11. أمثلة على البحث عن رقم في صفيف
12. 1. البحث الخطي
13. 2. بحث ثنائي
14. 3. باستخدام أساليب الصفيف المضمنة
15. طريقة الفهرس ()
16. البحث()
17. طريقة فيندكس () طريقة
18. 4. باستخدام العودية
19. مثال على البحث عن رقم خطي
20. مثال على البحث عن الرقم الثنائي
21. مثال على البحث عن رقم الاستيفاء
22. سؤال وجواب

ما هو صفيف?

المصفوفة هي بنية بيانات تسمح لك بتخزين وتنظيم العديد من العناصر من نفس النوع داخل متغير واحد. يحتوي كل عنصر من عناصر المصفوفة على فهرس خاص به ، والذي يسمح لك بالوصول إلى عناصر المصفوفة.

المصفوفات هي أدوات البرمجة الرئيسية وتستخدم على نطاق واسع في العديد من لغات البرمجة. إنها تسمح لك بتخزين ومعالجة كمية كبيرة من البيانات بكفاءة.

يمكن أن تحتوي المصفوفات على عناصر من أي نوع بيانات: أرقام وسلاسل وقيم منطقية وحتى مصفوفات أخرى. من المهم ملاحظة أن فهارس المصفوفة تبدأ بـ 0 — وهذا يعني أن العنصر الأول من المصفوفة يحتوي على فهرس 0 ، والثاني يحتوي على فهرس 1 ، وهكذا.

.

يمكن أن تكون المصفوفات أحادية البعد أو متعددة الأبعاد. المصفوفة أحادية البعد هي مصفوفة تحتوي على عناصر مرتبة في سطر واحد. المصفوفات متعددة الأبعاد عبارة عن مصفوفات تحتوي على عناصر مرتبة في جدول أو شبكة.

مثال على مصفوفة أحادية البعد:

أرقام فار= [1, 2, 3, 4, 5];

مثال على مصفوفة متعددة الأبعاد:

مصفوفة فار = [

[1, 2, 3],

[4, 5, 6],

[7, 8, 9]

];

المصفوفات هي أداة قوية عند العمل مع البيانات وتستخدم على نطاق واسع في البرمجة لحل المهام المختلفة.

طرق البحث عن رقم في صفيف

هناك عدة طرق للبحث عن رقم في صفيف. كل طريقة لها خصائصها وفعاليتها. في هذا القسم ، سنلقي نظرة على الطرق الأكثر شيوعا.

طريقة البحث الخطي

طريقة البحث الخطي هي الطريقة الأبسط والأكثر شيوعا للعثور على رقم في صفيف. وهو يتألف من مقارنة كل عنصر من عناصر المصفوفة بالتسلسل مع الرقم المطلوب.

الخوارزمية:

1. نذهب من خلال مجموعة من الأول إلى العنصر الأخير.
2. نقارن كل عنصر بالرقم المطلوب.
3. إذا كان العنصر يساوي الرقم المطلوب ، فإننا نعيد فهرسه.
4. إذا وصلنا إلى نهاية المصفوفة ولم يتم العثور على الرقم المطلوب ، فإننا نعود -1.

طريقة البحث الثنائي

تنطبق طريقة البحث الثنائي فقط على المصفوفات المصنفة. يعمل عن طريق تقسيم المصفوفة إلى جزأين ومقارنة الرقم المطلوب بالعنصر المركزي لكل جزء.

الخوارزمية:

1. وضعنا الحدود اليسرى واليمنى للبحث.
2. طالما أن الحد الأيسر لا يتجاوز الحد الأيمن ، فإننا نقوم بالإجراءات التالية:
1. نجد منتصف المصفوفة.
2. نقارن الرقم المطلوب مع العنصر المركزي.
3. إذا كان الرقم المطلوب يساوي العنصر المركزي ، فإننا نعيد فهرسه.
4. إذا كان الرقم المطلوب أقل من العنصر المركزي ، فقم بتحديث الحد الأيمن.
5. إذا كان الرقم المطلوب أكبر من العنصر المركزي ، فقم بتحديث الحد الأيسر.
3. إذا لم يتم العثور على الرقم المطلوب ، فقم بإرجاع -1.

طريقة البحث الاستيفاء

تستخدم طريقة البحث الاستيفاء الاستيفاء الخطي للعثور على الموضع التقريبي للرقم المطلوب في مصفوفة يفترض أنها موزعة بالتساوي.

الخوارزمية:

1. وضعنا الحدود اليسرى واليمنى للبحث.
2. طالما أن الحد الأيسر لا يتجاوز الحد الأيمن والرقم المطلوب داخل الحدود ، فإننا نقوم بتنفيذ الإجراءات التالية:
1. نحسب الموضع التقريبي للرقم المطلوب.
2. نقارن الرقم المطلوب بعنصر صفيف في موضع تقريبي.
3. إذا كان الرقم المطلوب يساوي العنصر في الموضع التقريبي ، فإننا نعيد فهرسه.
4. إذا كان الرقم المطلوب أقل من العنصر في الموضع التقريبي ، فقم بتحديث الحد الأيمن.
5. إذا كان الرقم المطلوب أكبر من العنصر في الموضع التقريبي ، فقم بتحديث الحد الأيسر.
3. إذا لم يتم العثور على الرقم المطلوب ، فقم بإرجاع -1.

طرق البحث باستخدام الوظائف القياسية

تحتوي لغات البرمجة مثل بايثون أو جافا سكريبت أيضا على وظائف مضمنة للبحث عن رقم في مصفوفة.:

• المدمج في" إندكسوف " وظيفة: إرجاع مؤشر أول حدوث الرقم المطلوب في مجموعة. إذا لم يتم العثور على الرقم ، بإرجاع -1.
• المدمج في وظيفة "البحث" : إرجاع العنصر الأول من المصفوفة التي تفي بشرط الوظيفة المحددة. إذا لم يكن هناك مثل هذا العنصر ، فإنه يعود "غير محدد".
• المدمج في وظيفة" فيندندكس": إرجاع مؤشر العنصر الأول من المصفوفة التي تفي بشرط الوظيفة المحددة. إذا لم يكن هناك مثل هذا العنصر ، يعود -1.

يعتمد اختيار طريقة البحث عن رقم في صفيف على حجمه وفرز المصفوفة ومتطلبات الأداء. استخدم الطريقة المناسبة على أساس كل حالة على حدة.

البحث عن الرقم الخطي

يعد البحث الخطي أحد أبسط الخوارزميات وأكثرها شيوعا للبحث عن رقم في مصفوفة. تقوم هذه الطريقة بتمرير متسلسل عبر عناصر المصفوفة ، ومقارنة كل عنصر بالرقم المطلوب.

تعمل خوارزمية البحث الخطي على النحو التالي:

1. نبدأ في مقارنة عناصر المصفوفة بالرقم المطلوب ، بدءا من العنصر الأول.
2. إذا كان العنصر الحالي يساوي الرقم المطلوب ، فقد وجدنا الرقم المطلوب في المصفوفة وننهي البحث.
3. إذا كان العنصر الحالي لا يساوي الرقم المطلوب ، فإننا نواصل المقارنة مع العنصر التالي.
4. كرر الخطوتين 2 و 3 حتى يتم فحص جميع العناصر في المصفوفة.
5. إذا لم يتم العثور على الرقم المطلوب بعد التحقق من جميع العناصر ، فيمكننا أن نستنتج أن الرقم المطلوب ليس في المصفوفة.

مثال على تنفيذ البحث الخطي عن الأرقام في جافا سكريبت:

وظيفة البحث الخطي (آر ، الهدف) {

إلى عن على (دعني = 0 ؛ أنا < آر.الطول ؛ أنا {) {

إذا (آر[أنا]=== الهدف) {

العودة أنا ؛ / / إرجاع فهرس الرقم الذي تم العثور عليه

}

}

إرجاع -1 ؛ / / إرجاع -1 إذا لم يكن هناك رقم مطلوب في المصفوفة

}

أرقام كونست = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

كونست هدفرقم = 5;

نتيجة كونست = البحث الخطي(أرقام ، رقم الهدف);

وحدة التحكم.سجل (نتيجة);

يقبل وسيطتين: صفيف والرقم المطلوب. يمر بالتتابع من خلال عناصر المصفوفة باستخدام الحلقة. إذا تم العثور على رقم يساوي الرقم الذي تبحث عنه ، فإن الدالة ترجع فهرسها. إذا لم يتم العثور على الرقم المطلوب ، ترجع الدالة -1.

البحث الخطي هو خوارزمية بسيطة وبديهية ، ولكن له بعض العيوب. العيب الرئيسي للبحث الخطي هو تعقيد وقته-س (ن) ، أين ن هو عدد العناصر في المصفوفة. مع المصفوفات الكبيرة ، يمكن إبطاء البحث بشكل كبير. بالإضافة إلى ذلك ، يجد البحث الخطي العنصر الأول فقط مساويا للرقم المطلوب ، إذا كان هناك العديد من هذه العناصر. في هذه الحالة ، قد تحتاج إلى استخدام طرق بحث أخرى للعثور على جميع التكرارات.

البحث عن رقم ثنائي

البحث الثنائي هو أحد الخوارزميات الرئيسية للبحث عن عنصر في مصفوفة مرتبة. يعمل في ا (سجل ن) الوقت ، أين ن هو عدد العناصر في المصفوفة. هذا يجعلها فعالة للغاية عند العمل مع كميات كبيرة من البيانات.

تعمل خوارزمية البحث الثنائي على النحو التالي:

1. يتم تعيين مصفوفة مرتبة يتم فيها إجراء البحث.
2. يتم تعيين حدود البحث: يتم تعيين المؤشر المنخفض الأولي على 0 ويتم تعيين المؤشر العالي النهائي على آخر فهرس للمصفوفة.
3. حتى يصبح منخفض أعلى من مرتفع ، يتم تنفيذ العمليات التالية:
4. إذا انتهت الحلقة ، فإن الرقم المطلوب مفقود من المصفوفة ويتم إرجاع قيمة خاصة ، على سبيل المثال ، -1 ، للإشارة إلى عدم وجود نتيجة.

البحث الثنائي فعال لأنه في كل تكرار للخوارزمية ، يتم تقسيم المصفوفة إلى النصف ، ويتم تقليل عدد العناصر المحددة إلى النصف مع كل تكرار.

البحث الثنائي هو أحد طرق البحث الأساسية في البرمجة ويستخدم على نطاق واسع في المهام المختلفة حيث يلزم البحث السريع عن العناصر في البيانات المرتبة. نظرا لفعاليتها ، فإن هذه الخوارزمية تستحق الدراسة والاستخدام في مشاريعك.

البحث عن رقم الاستيفاء

البحث عن رقم الاستيفاء هو خوارزمية فعالة للعثور على رقم في مصفوفة مرتبة بناء على الاستيفاء الخطي.

الفكرة الرئيسية لبحث الاستيفاء هي أنه يمكننا تقريبا افتراض موضع العنصر المطلوب في المصفوفة بناء على قيمته وقيم العنصرين الأول والأخير من المصفوفة.

خوارزمية البحث الاستيفاء هي كما يلي:

1. نفترض أن العنصر يقع تقريبا في منتصف المصفوفة.
2. نجد موضع الاستيفاء باستخدام الصيغة:
3. إذا كانت القيمة في موضع الاستيفاء تتطابق مع القيمة التي تبحث عنها ، فإننا نعيدها.
4. إذا كانت القيمة في موضع الاستيفاء أكبر من القيمة المطلوبة ، فإن الرقم المطلوب يقع بين قيم العناصر ذات المواضع المنخفضة ونقاط البيع -1. يستمر البحث في النصف الأيسر من المصفوفة.
5. إذا كانت القيمة في موضع الاستيفاء أقل من القيمة المطلوبة ، فإن الرقم المطلوب يكون بين قيم العناصر ذات المواضع نقاط البيع + 1 وعالية. يستمر البحث في النصف الأيمن من المصفوفة.
6. كرر الخطوات من 2 إلى 5 حتى يتم العثور على الرقم المطلوب أو يبقى عنصر واحد فقط من المصفوفة.

يسمح لك البحث عن رقم الاستيفاء بالعثور على القيمة المطلوبة بشكل أسرع من البحث الخطي العادي إذا تم توزيع عناصر المصفوفة بالتساوي.

ومع ذلك ، يجب ألا يغيب عن البال أنه في بعض الحالات قد لا يكون بحث الاستيفاء فعالا ويتحول إلى بحث خطي منتظم ، خاصة إذا لم يتم توزيع القيم الموجودة في المصفوفة بالتساوي.

مثال على كود بايثون:

ديف الاستيفاء_البحوث(آر ، س):

منخفض = 0

عالية = لين (أر) - 1

في حين منخفضة = أر [منخفضة] و س < = أر [عالية]:

نقاط البيع = منخفض + كثافة العمليات (((عالية - منخفضة) / (أر[عالية] - أر[منخفضة])) * (س-أر [منخفضة]))

if arr[pos] == x:

return pos

elif arr[pos] < x:

low = pos + 1

else:

high = pos - 1

return -1

# Пример использования функции

arr = [10, 20, 30, 40, 50, 60, 70]

x = 40

result = interpolation_search(arr, x)

if result != -1:

print("Число", x, "найдено на позиции", result)

else:

print("Число", x, "не найдено в массиве")

Хэш-таблицы для поиска числа

جداول التجزئة هي بنية بيانات توفر طريقة فعالة للبحث عن العناصر. وهي تستند إلى مبدأ التجزئة ، حيث يتم تعيين مفتاح تجزئة فريد لكل عنصر. تسمح لك جداول التجزئة بالعثور بسرعة على عنصر من خلال مفتاحه.

للبحث عن رقم في مصفوفة باستخدام جدول تجزئة ، اتبع الخطوات التالية:

1. إنشاء جدول تجزئة.
2. تذهب من خلال مجموعة من الأرقام وحساب التجزئة لكل رقم ، والتي سيتم استخدامها كمفتاح لجدول التجزئة.
3. أضف كل رقم وتجزئته إلى جدول التجزئة.
4. إذا لزم الأمر ، يمكنك التحقق من وجود رقم في جدول التجزئة من خلال التجزئة الخاصة به.

مزايا استخدام جداول التجزئة للعثور على الأرقام:

• الوصول السريع إلى العناصر. يتم إجراء البحث في جدول التجزئة في وقت ثابت س (1) ، مما يعني أن وقت البحث لا يعتمد على عدد العناصر في جدول التجزئة.
• الاستخدام الفعال للذاكرة. توفر جداول التجزئة عمليات بحث سريعة عن الذاكرة باستخدام التجزئة ، مما يقلل من مقدار الذاكرة المستخدمة.

جداول التجزئة هي أداة فعالة للعثور على الأرقام في صفيف. إنها تسمح لك بتقليل وقت تنفيذ البحث واستخدام الذاكرة بشكل أكثر كفاءة. ومع ذلك ، عند استخدام جداول التجزئة ، من الضروري مراعاة إمكانية حدوث تصادمات - المواقف التي يتم فيها تعيين عنصرين مختلفين لنفس التجزئة. يتم استخدام طرق مختلفة لحل هذه المشكلة ، مثل طريقة التسلسل أو العنونة المفتوحة.

أمثلة على البحث عن رقم في صفيف

فيما يلي بعض الأمثلة للبحث عن رقم في مصفوفة باستخدام طرق مختلفة.

1. البحث الخطي

البحث الخطي هو أبسط الطرق وأكثرها وضوحا للعثور على رقم في مصفوفة. وهو يتألف من التكرار المتسلسل من خلال كل عنصر من عناصر المصفوفة حتى يتم العثور على الرقم المطلوب أو يتم اجتياز جميع عناصر المصفوفة.

وظيفة البحث الخطي (آر ، الهدف) {

إلى عن على (دعني = 0 ؛ أنا < آر.الطول ؛ أنا {) {

إذا (آر[أنا] === الهدف) {

عودة أنا;

}

}

عودة -1;

}

أرقام كونست = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

عدد الأهداف = 7;

مؤشر كونست = البحث الخطي (الأرقام ، رقم الهدف);

وحدة التحكم.سجل (فهرس) ؛ / / الإخراج: 6

2. بحث ثنائي

يتم تطبيق البحث الثنائي فقط على المصفوفات المصنفة. يبدأ بمقارنة الرقم المطلوب بالعنصر الموجود في منتصف المصفوفة ، وإذا كان أكبر أو أصغر ، يقسم المصفوفة إلى نصفين. Затем процесс повторяется для подмассива, содержащего искомое число, пока число не будет найдено или не останется один элемент.

function binarySearch(arr, target) {

let start = 0;

let end = arr.length - 1;

while (start <= end) {

let mid = Math.floor((start + end) / 2);

if (arr[mid] === target) {

return mid;

} else if (arr[mid] < target) {

start = mid + 1;

} else {

end = mid - 1;

}

}

return -1;

}

const numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

const targetNumber = 7;

مؤشر كونست = بيناريسيرتش (أرقام ، رقم الهدف);

وحدة التحكم.سجل (فهرس) ؛ / / الإخراج: 6

3. باستخدام أساليب الصفيف المضمنة

.

إرجاع فهرس التكرار الأول للرقم المطلوب في المصفوفة ، أو -1 إذا لم يتم العثور على الرقم.

أرقام كونست = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

عدد الأهداف = 7;

مؤشر كونست = أرقام.مؤشر (رقم الهدف);

وحدة التحكم.سجل (فهرس) ؛ / / الإخراج: 6

الطريقة

إرجاع العنصر الأول من الصفيف الذي يفي بالشرط المحدد في دالة رد الاتصال التي تم تمريرها.

أرقام كونست = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

عدد الأهداف = 7;

تم العثور على رقم = أرقام.ابحث عن ((رقم) = > رقم = = = رقم الهدف);

وحدة التحكم.سجل (تم العثور عليهرقم) ؛ / / الإخراج: 7

الطريقة

إرجاع فهرس العنصر الأول من الصفيف الذي يفي بالشرط المحدد في دالة رد الاتصال التي تم تمريرها ، أو -1 إذا لم يتم العثور على مثل هذا العنصر.

أرقام كونست = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

عدد الأهداف = 7;

مؤشر كونست = أرقام.فيندكس ((عدد) = > عدد = = = تارجيتنومبر);

وحدة التحكم.سجل (فهرس) ؛ / / الإخراج: 6

4. باستخدام العودية

تتمثل الطريقة العودية لإيجاد رقم في مصفوفة في تقسيم المصفوفة إلى نصفين والبحث المتكرر عن أحد النصفين. إذا تم العثور على رقم ، يتم إرجاع فهرسه ، وإلا يتم إرجاع -1.

وظيفة ريكورسيفيرتش (آر ، الهدف ، بداية ، نهاية) {

إذا (بداية > نهاية) {

عودة -1;

}

دعونا منتصف = الرياضيات.الطابق ((البداية + النهاية) / 2);

إذا (آر [منتصف] = = = الهدف) {

عودة منتصف;

} آخر إذا (آر[منتصف] < الهدف) {

عودة ريكورسيفيرتش(أر ، الهدف ، منتصف + 1 ، نهاية);

} آخر {

عودة ريكورسيفيرتش(أر ، الهدف ، بداية ، منتصف 1);

}

}

أرقام كونست = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

عدد الأهداف = 7;

مؤشر كونست = ريكورسيفيرش (أرقام ، تارجيتنومبر ، 0 ، أرقام.الطول-1);

وحدة التحكم.سجل (فهرس) ؛ / / الإخراج: 6

Пример линейного поиска числа

البحث الخطي هو أبسط وأبسط طريقة للبحث عن رقم في مصفوفة. يقوم بالبحث عن طريق مقارنة كل عنصر من عناصر المصفوفة بالتسلسل مع الرقم المستهدف.

لنلق نظرة على مثال للبحث الخطي عن الرقم 5 في صفيف:

// المصفوفة الأصلية

إنت [] آر = {2, 4, 6, 8, 10, 12, 14, 16};

كثافة العمليات الهدف = 5 ؛ / / العدد المستهدف

// البحث الخطي

مؤشر كثافة العمليات = -1 ؛ / / متغير لتخزين فهرس الرقم الموجود

إلى عن على (الباحث الأول = 0; أنا < آر.الطول ؛ أنا {) {

إذا (أر [أنا] = = الهدف) {

الفهرس = أنا;

كسر ؛ / / تم العثور على رقم ، نخرج من الحلقة

}

}

إذا (مؤشر != -1) {

النظام.خارج.برينتلن ("عدد" + الهدف + "وجدت في مجموعة ، فهرسها:" + مؤشر);

} آخر {

النظام.خارج.برينتلن ("الرقم" + الهدف + "غير موجود في المصفوفة");

}

في هذا المثال ، نبحث عن الرقم 5 في المصفوفة {2, 4, 6, 8, 10, 12, 14, 16}. بمقارنة كل عنصر من عناصر المصفوفة بالتسلسل مع الرقم المستهدف ، نجده في الموضع الخامس ونقطع الدورة. ونتيجة لذلك ، نحصل على الإخراج:"تم العثور على الرقم 5 في المصفوفة ، ومؤشره هو 4".

البحث الخطي سهل التنفيذ ، لكن فعاليته تقل عند العمل مع المصفوفات الكبيرة. في مثل هذه الحالات ، يوصى باستخدام خوارزميات البحث عن الأرقام المحسنة ، مثل البحث الثنائي أو جداول التجزئة.

مثال على البحث عن الرقم الثنائي

البحث عن الرقم الثنائي هو خوارزمية فعالة للبحث عن قيمة في مصفوفة مرتبة. لنلق نظرة على مثال بسيط للبحث الثنائي عن الرقم 7 في المصفوفة المصنفة التالية:

[1, 3, 4, 6, 7, 9, 11]

1. قمنا بتعيين القيم الأولية للمتغيرات منخفضة (الحد الأدنى) وعالية (الحد الأعلى) إلى 0 وطول الصفيف ناقص 1 ، على التوالي.
2. نحسب متوسط مؤشر منتصف كما تقسيم عدد صحيح من مجموع منخفضة وعالية بنسبة 2.
3. مع الرقم المطلوب 7.
4. إذا كان 7 ، ثم يتم العثور على عدد ونعود مؤشر منتصف.
5. إذا كان أكبر من 7 ، فإننا نقوم بتحديث قيمة المتغير العالي إلى منتصف 1 وننتقل إلى الخطوة 2.
6. إذا كان أقل من 7 ، فإننا نقوم بتحديث قيمة المتغير المنخفض إلى منتصف + 1 وننتقل إلى الخطوة 2.
7. كرر الخطوات من 2 إلى 6 حتى تصبح قيمة المتغير المنخفض أكبر من قيمة المتغير العالي.
8. عندما تصبح قيمة المتغير المنخفض أكبر من قيمة المتغير العالي ، فهذا يعني أن الرقم غير موجود في المصفوفة ، ونعيد القيمة -1.

في مثالنا ، حالة الرقم 7:

1. منخفض = 0 ، مرتفع = 6 ، متوسط = 3;
2. صفيف [منتصف] = 6 ، وهو أقل من 7;
3. تغيير منخفض إلى منتصف + 1 ، أي منخفض = 4;
4. كرر الخطوات من 2 إلى 6;
5. منخفض = 4 ، مرتفع = 6 ، متوسط = 5;
6. صفيف [منتصف] = 9 ، وهو أكبر من 7;
7. تغيير عالية إلى منتصف 1 ، وهذا هو ، عالية = 4;
8. منخفض > مرتفع ، عائد -1;

وبالتالي ، لم يتم العثور على الرقم 7 في المصفوفة.

يعد البحث عن الأرقام الثنائية فعالا ويسمح لك بالعثور على القيم في المصفوفات المصنفة باستخدام مقارنات أقل بكثير من البحث الخطي.

مثال على البحث عن رقم الاستيفاء

بحث الاستيفاء هو خوارزمية بحث ثنائية محسنة تعمل مع مجموعة مرتبة من الأرقام. على عكس البحث الثنائي ، فإنه لا يستخدم فقط منتصف المصفوفة ، ولكن أيضا قيمة الرقم نفسه للاقتراب من القيمة المطلوبة.

تتكون عملية البحث الاستيفاء من التسلسل التالي من الإجراءات:

1. منتصف = منخفض + ((مرتفع-منخفض) / (أر [مرتفع] - أر[منخفض])) * (س-أر[منخفض])
2. قارن قيمة عنصر مع فهرس
3. عالية

).

كرر الخطوات من 1 إلى 2 حتى يتم العثور على الرقم المطلوب أو حتى يتم فحص جميع عناصر المصفوفة.

هنا مثال على تنفيذ البحث الاستيفاء في بيثون:

ديف الاستيفاء_البحوث(آر ، س):

منخفض = 0

عالية = لين (أر) - 1

while low = arr[low] and x <= arr[high]:

if low == high:

if arr[low] == x:

return low

return -1

pos = low + ((high - low) // (arr[high] - arr[low])) * (x - arr[low])

if arr[pos] == x:

return pos

elif arr[pos] < x:

low = pos + 1

else:

high = pos - 1

return -1