أيه أحسن طريقة أبحث بيها جوا sorted array ؟! ..

[x32x01]

- دلوقتي يا زعيم لو إحنا عندنا sorted array أي أحسن طريقة ( algorithm ) أبحث بيها عن عنصر جوا الـ array دي ؟

أول ما تشوف كلمة sorted array سواء ASC أو DESC - ( ترتيب تنازلي أو تصاعدي )​

يبقي علطول الاختيار الأمثل هو Binary Search

عشان نعرف الـ Binary Search وبيوفر علينا اد ايه ، هنقارنه بالـ linear search واللي هي طريقة بحث برضو ، في مثال كده نفهم منه إن شاء الله​

المثال
- لو عندنا array بيبدأ من رقم 1 لحد رقم 100
وعاوز ادور علي رقم مثلا 67 ..

الطريقة الأولي: هنستخدم Linear search​

هنقعد نمشي في الـ array رقم وراه التاني لحد ما نوصل لـ الهدف بتاعنا .. في الطريقة دي احنا مشينا 67 خطوة لحد ما وصلنا للهدف بتاعنا
وده الـ Big O بتاعه هو O

الطريقة التانية : هنستخدم Binary Search​

بس طريقة البحث هنا مختلفة شوية ، بس اضمنلك اسرع ، تعالي نعد الخطوات
الخطوة الأولي : هنقسم الـ array بتاعنا لنصين بالتساوي يعني الـ array الرئيسية بتاعتنا هتتحول لـعدد اتنين array
الـ array الاول هيبدأ من 1 لحد 50 ( هنستبعده )
والـ array التاني هيبدأ من 51 لحد 100 ( هنبحث فيه )
لو نسيت فا احنا كنا بندور علي رقم 67 ..
هنيجي نشوف رقم 67 هل بيقع في الرنچ بتاع الـ array الأول اللي هو من 1 لـ 50 ؟ هنلاقي أنه لأ فـ هنتجاهل الـ array الاول كله عشان مفهوش الرقم من غير ما ندور جواه اصلا .. في الحالة دي احنا وفرنا أننا نقطع مسافة 50 خطوة بندور علي الرقم بتاعنا

الخطوة التانية : نبدأ بقي نشتغل في الـ array التاني اللي كان بيبدأ من 51 لحد 100 وهنقسمه لاتنين array بالتساوي برضو هتلاقي
أن بقي عندي اتنين array
الـ array الاول من 51 لحد 75 ( هنبحث فيه )
والـ array التاني من رقم 76 لحد 100( هنستبعده )
انت اكيد بقيت عارف هنعمل اي

الخطوة التالتة : هنلاقي أن الرقم موجود عندي في الـ array الاول اللي من 51 لحد 75 بس لسه موصلناش للرقم بالظبط.. فا هنقسمه لاتنين array برضو
الـ array الأول هيكون من 51 لحد 62 ( هنستبعده)
والـ array التانية هيكون من 63 لحد 75 ( هنبحث فيه )
انت بقيت عارف هنعمل اي .. هنتجاهل الـ array الاول عشان الرقم اللي بندور عليه مش موجود جواه ونخش في الـ array التاني علطول

الخطوة الرابعة : هنقسم الـ array اللي من 63 لحد 75 لاتنين
الـ array الأول هتكون من 63 لحد 69 ( هنبحث فيه )
والـ array التاني هيكون من 70 لحد 75 ( هنستبعده )

الخطوة الخامسة : هنقسم الـ array لاتنين تاني
الـ array الأول : من 63 لـ 66 ( هنستبعده )
الـ array التاني : من 67 لـ 69 ( هنبحث فيه )

الخطوة السادسة والأخيرة : هنا هنجيب النصف بالظبط
mid = Math.floor((69 + 67) / 2 ) = 67
وكده الحمد لله أحنا وصلنا للنتيجة في 6 خطوات بس
و time complexity بـ O( log)
بدل ما في الطريقة الأولي كنا مشينا الـ 67 كاملين لحد ما وصلنا للرقم اللي بندور عليه .. وبـ O
طبعا حابب أنوه طريقة الـ binary Search لازم الـ Array يكون فيها sorted
وده كود js بينفذ الـ Binary Search عشان لو حد حابب يجرب