- بواسطة x32x01 ||
يعنى ايه Binary search وليه معظم الشركات الكبيرة بتستخدمه ؟!!
كوباية الشاى بتاعتك بقا وركز معايا كدا علشان هنفهم يعنى ايه Binary search وايه الفرق بينه وبين Linear search وايه عيوبه
- - - هضربلك مثال كالعادة هيوضحلك بيشتغل ازاى
لنفترض انك عندك كتاب صفحاته مرقمة من 1 الى 100 وانتا عايز تقرأ حاجه فى الكتاب وموجودة فى صفحة 78 مثلا فهتحتاج انك تبحث على الصفحة دى جوا الكتاب وهتلاقى انك عندك طريقتين :
أ - هتمسك الكتاب من اوله وهتشوف رقم كل صفحة وتشوف هيا الصفحة اللى انتا عايزها ولا لأ
- ولو مش هيا الصفحة هتروح للصفحة اللى بعدها وتقارن بردو وهتفضل ماشى كدا لحد لما تلاقى الصفحة اللى انتا عايزها
- وبكدا انتا هتمشى على معظم صفحات الكتاب وهتاخد وقت كتير شوية فى الطريقة دى
ب - هتروح للصفحة اللى فى نص الكتاب ( صفحة 50 مثلا ) وهتشوف هيا رقمها بيساوى رقم الصفحة اللى انتا عايزها فهتلاقى انها مش هيا الصفحة اللى انتا عايزها
- هتقارن رقم الصفحة اللى انتا عايزها بالصفحة دى ( هتلاقى ان رقم الصفحة اللى انتا عايزها اكبر من رقم الصفحة اللى فى نص الكتاب )
- فكدا مستحيل الصفحة اللى انتا عايزها تكون فى النص الاول من الكتاب ( من صفحة 1 الى صفحة 49 )
- كدا انتا عرفت ان الصفحة اللى انتا عايزها موجودة فى النص التانى من الكتاب
- وكدا نص الكتاب الاول انتا مش هتبحث فيه تانى وهتبحث جوا النص التانى
- هتروح للنص التانى من الكتاب وتروح للصفحة اللى موجودة فى نص الجزء ده من الكتاب ( صفحة 75 )
- هتقارن رقم الصفحة اللى انتا عايزها بالصفحة دى فهتلاقى انها مش هيا الصفحة اللى انتا عايزها ( هتلاقى ان رقم الصفحة اللى انتا عايزها اكبر من رقم الصفحة دى )
- فكدا مستحيل الصفحة اللى انتا عايزها تكون فى النص الاول من الجزء التانى من الكتاب ( من صفحة 51 الى صفحة 74)
- هتكرر الخطوات دى لحد ما تلاقى رقم الصفحة اللى انتا عايزها
خلينا بقا نروح لل data structure
- اللى انتا عملته فى الطريقة الاولى علشان تبحث عن رقم صفحة معينة داخل مجموعة من ارقام صفحات تانيه اسمه ( Linear search )
- الطريقة التانيه دى اسمها ( Binary search )
وطبعا الطريقة التانيه افضل من الطريقة الاولى من غير تفكير بس فى مشكلة واحدة بس
ان مجموعة البيانات ( ارقام الصفحات ) اللى انتا هتبحث عن شئ داخلها ( رقم الصفحة اللى انتا عايزه ) لازم تكون ( مترتبة )
- يعنى زى الكتاب مثلا صفحاته مترتبة من 1 الى 100
- - ال time complexity in worst case للطريقتين هيا كالتالى :
الـ worst case بالنسبة لعملية البحث ان العنصر يكون فى اخر مجموعة العناصر
أ - O( n ) بالنسبة للطريقة الاولى ( لو انتا العنصر اللى انتا عايزه فى اخر مجموعة العناصر فانتا هتحتاج تمر على العناصر كلها يعنى لو عندك 1000 عنصر هتحتاج تمشى 1000 خطوة علشان تلاقى العنصر اللى انتا محتاجه )
ب - O( logn ) بالنسبة للطريقة التانيه ( لو انتا العنصر اللى انتا عايزه فى اخر مجموعة العناصر وعدد العناصر بتاعتك 1000 عنصر فانتا هتحتاج تمشى 10 خطوات علشان تلاقى العنصر اللى انتا محتاجه )
كوباية الشاى بتاعتك بقا وركز معايا كدا علشان هنفهم يعنى ايه Binary search وايه الفرق بينه وبين Linear search وايه عيوبه
- - - هضربلك مثال كالعادة هيوضحلك بيشتغل ازاى
لنفترض انك عندك كتاب صفحاته مرقمة من 1 الى 100 وانتا عايز تقرأ حاجه فى الكتاب وموجودة فى صفحة 78 مثلا فهتحتاج انك تبحث على الصفحة دى جوا الكتاب وهتلاقى انك عندك طريقتين :
أ - هتمسك الكتاب من اوله وهتشوف رقم كل صفحة وتشوف هيا الصفحة اللى انتا عايزها ولا لأ
- ولو مش هيا الصفحة هتروح للصفحة اللى بعدها وتقارن بردو وهتفضل ماشى كدا لحد لما تلاقى الصفحة اللى انتا عايزها
- وبكدا انتا هتمشى على معظم صفحات الكتاب وهتاخد وقت كتير شوية فى الطريقة دى
ب - هتروح للصفحة اللى فى نص الكتاب ( صفحة 50 مثلا ) وهتشوف هيا رقمها بيساوى رقم الصفحة اللى انتا عايزها فهتلاقى انها مش هيا الصفحة اللى انتا عايزها
- هتقارن رقم الصفحة اللى انتا عايزها بالصفحة دى ( هتلاقى ان رقم الصفحة اللى انتا عايزها اكبر من رقم الصفحة اللى فى نص الكتاب )
- فكدا مستحيل الصفحة اللى انتا عايزها تكون فى النص الاول من الكتاب ( من صفحة 1 الى صفحة 49 )
- كدا انتا عرفت ان الصفحة اللى انتا عايزها موجودة فى النص التانى من الكتاب
- وكدا نص الكتاب الاول انتا مش هتبحث فيه تانى وهتبحث جوا النص التانى
- هتروح للنص التانى من الكتاب وتروح للصفحة اللى موجودة فى نص الجزء ده من الكتاب ( صفحة 75 )
- هتقارن رقم الصفحة اللى انتا عايزها بالصفحة دى فهتلاقى انها مش هيا الصفحة اللى انتا عايزها ( هتلاقى ان رقم الصفحة اللى انتا عايزها اكبر من رقم الصفحة دى )
- فكدا مستحيل الصفحة اللى انتا عايزها تكون فى النص الاول من الجزء التانى من الكتاب ( من صفحة 51 الى صفحة 74)
- هتكرر الخطوات دى لحد ما تلاقى رقم الصفحة اللى انتا عايزها
خلينا بقا نروح لل data structure
- اللى انتا عملته فى الطريقة الاولى علشان تبحث عن رقم صفحة معينة داخل مجموعة من ارقام صفحات تانيه اسمه ( Linear search )
- الطريقة التانيه دى اسمها ( Binary search )
وطبعا الطريقة التانيه افضل من الطريقة الاولى من غير تفكير بس فى مشكلة واحدة بس
ان مجموعة البيانات ( ارقام الصفحات ) اللى انتا هتبحث عن شئ داخلها ( رقم الصفحة اللى انتا عايزه ) لازم تكون ( مترتبة )
- يعنى زى الكتاب مثلا صفحاته مترتبة من 1 الى 100
- - ال time complexity in worst case للطريقتين هيا كالتالى :
الـ worst case بالنسبة لعملية البحث ان العنصر يكون فى اخر مجموعة العناصر
أ - O( n ) بالنسبة للطريقة الاولى ( لو انتا العنصر اللى انتا عايزه فى اخر مجموعة العناصر فانتا هتحتاج تمر على العناصر كلها يعنى لو عندك 1000 عنصر هتحتاج تمشى 1000 خطوة علشان تلاقى العنصر اللى انتا محتاجه )
ب - O( logn ) بالنسبة للطريقة التانيه ( لو انتا العنصر اللى انتا عايزه فى اخر مجموعة العناصر وعدد العناصر بتاعتك 1000 عنصر فانتا هتحتاج تمشى 10 خطوات علشان تلاقى العنصر اللى انتا محتاجه )