Binary Searchlo · mid · hi · lower bound · binary search on the answer
في الفصل اللي فات اتعلمنا نرتّب الداتا ونشتغل على intervals. دلوقتي هنقبض تمن الترتيب ده: لو الداتا مترتبة، مش محتاج تبص على كل عنصر. بتبص في النص وترمي نص الـ search space في كل خطوة، فمليون عنصر بيخلصوا في 20 خطوة. والأهم إنك تكتبه صح من أول مرة، من غير off-by-one ولا infinite loop.
هتطلع من الفصل ده وإنت عارف
- تقول بالكلام
[lo, hi]معناه إيه، وتطلّع منه لوحدك:<=ولا<، وmid + 1ولاmid، وhi = nولاn - 1. - تكتب 3 templates من دماغك: exact value، و first true، و last true، وتعرف إمتى كل واحد.
- تشوف بعينك ليه الكود بيعلّق في infinite loop لما تنسى الـ
+ 1. - تعمل binary search على الإجابة نفسها لما مفيش array مترتبة خالص، وتحل 704 و 35 و 34 و 153 و 33 و 875 و 1011 و 69.
ليه Binary Search؟
عندك array مترتبة، وعايز تعرف رقم معين موجود ولا لأ، وفين. أول حل بييجي في دماغك: linear search، تمشي عليها واحدة واحدة.
ده O(n): في الـ worst case بيبص على كل العناصر. ولو المسألة بتسأل السؤال ده 10⁵ مرة على array فيها 10⁵ عنصر، يبقى 10¹⁰ عملية و TLE أكيد. بص عليه وهو بيدوّر على 25:
9 مقارنات على 10 أرقام. والمشكلة إنه ما استفادش من الترتيب خالص: لما شاف الـ 12، كان المفروض يفهم إن الـ 25 مش على شمالها.
نفس الـ array ونفس الـ 25، بس المرة دي بنبص في النص الأول. الخانات اللي اترمت بتبهت:
3 مقارنات بدل 9، والفرق بيكبر بسرعة رهيبة:
n | linear (worst case) | binary (worst case) |
|---|---|---|
| 10 | 10 | 4 |
| 1,000 | 1,000 | 10 |
| 1,000,000 | 1,000,000 | 20 |
| 1,000,000,000 | 1,000,000,000 | 30 |
الـ key insight: كل مقارنة بتقسم الباقي على 2، فالسؤال بقى «أقسم n على 2 كام مرة لحد ما يفضل عنصر واحد؟». الإجابة log₂ n، يعني O(log n) (راجع Big-O لو محتاج). كل ما تضاعف n، binary search بيزيد one step بس.
طب إزاي تعرف من كلام المسألة إنها binary search، حتى لو مفيهاش array مترتبة أصلًا؟
إزاي تعرفه من المسألة
آخر 4 إشارات في أول قائمة مفيهمش array مترتبة خالص، ودول اللي بيوقّعوا الناس. binary search مش محتاج array مترتبة، هو محتاج سؤال إجابته بتتقلب مرة واحدة بس من «لأ» لـ «آه». ولو الـ array مش مترتبة ومطلوب تلاقي قيمة، ده شغل hash map.
| النوع | بتدوّر على إيه | الـ template | أشهر مسائل |
|---|---|---|---|
| قيمة بالظبط exact match | index رقم معين، أو -1 | Template 1: lo <= hi | 704، 74، 33 |
| أول مكان بيحقق شرط lower bound / first true | أول index الشرط فيه true | Template 2: lo < hi، hi = mid | 35، 34، 278، 153 |
| على الإجابة binary search on the answer | أصغر (أو أكبر) رقم ينفع | Template 2 أو 3 على range من الأرقام | 875، 1011، 69، 410 |
| Rotated rotated sorted array | زي اللي فوق، بس لازم تعرف أنهي نص مترتب | Template 1 أو 2 + شرط زيادة | 33، 153 |
flowchart TD
A["Binary search?"] --> B{"Sorted array, find one exact value?"}
B -- yes --> T1["Template 1: closed range, mid plus or minus 1"]
B -- no --> C{"First or last position that satisfies a condition?"}
C -- yes --> T2["Template 2: first true, hi = mid"]
C -- no --> D{"Answer is a number, and 'can I do it with x?' flips once?"}
D -- yes --> T3["Binary search on the answer: range of numbers + Template 2 or 3"]
D -- no --> E{"Sorted array that was rotated?"}
E -- yes --> R["Find the sorted half first"]
E -- no --> H["Probably another pattern: hash map, two pointers, prefix sum"]
اسأل نفسك الأسئلة دي بالترتيب ده.
قبل ما نكتب أي كود، فيه سؤال واحد لو جاوبته صح مش هتغلط off-by-one تاني: [lo, hi] معناه إيه؟
الفكرة اللي بتمنع الـ off-by-one: [lo, hi] معناه إيه؟
أغلب الناس حافظين binary search وبرضه بيغلطوا فيه: < بدل <=، أو mid بدل mid + 1، والكود يعلّق أو يفوّت الإجابة. السبب إنهم حافظين الشكل من غير المعنى. الحل إنك تكتب جملة واحدة قبل الكود، وكل سطر يمشي وراها.
«لو الـ target موجود، يبقى موجود في الخانات من
lo لحد hi، والاتنين داخلين.»
من الجملة دي بس هتطلّع كل سطر:
- البداية: الـ target ممكن يكون في أي حتة، فـ
lo = 0وhi = n - 1. ليهn - 1؟ عشانhiداخل في الـ range، وآخر خانة موجودة هيn - 1. - نكمّل لحد إمتى؟ طول ما الـ range فيه خانة واحدة على الأقل. لو
lo = hi = 3فيه خانة لسه ما اتبصّش عليها، فالشرطlo <= hi. والـ range بيفضى لماlo > hi. nums[mid] < target؟ الـmidوكل اللي شماله أصغر، فالـ target لو موجود فهو في[mid + 1, hi]:lo = mid + 1. والعكس:hi = mid - 1.- الـ loop خلصت؟ الـ range فاضي، والجملة بتقول «لو موجود فهو جوه range فاضي»، يعني مش موجود:
return -1.
الصورة الأعمّ: سؤال إجابته بتتقلب مرة واحدة
binary search في الحقيقة مش «دوّر على رقم». هو «لاقي الحد بين حتة الإجابة فيها لأ وحتة الإجابة فيها آه». خد array مترتبة واسأل كل خانة: «إنتِ >= 8؟»
كل الـ F الأول وبعدين كل الـ T، ومفيش F بيرجع. الشكل ده اسمه monotonic. وطول ما سؤالك ليه الشكل ده، تقدر تلاقي أول T في O(log n): لو mid طلع F، أول T على يمينه. لو T، أول T هو أو على شماله. ده سر «binary search على الإجابة» اللي هنوصله في Koko.
| الـ template | الـ invariant | الـ loop بتقف إمتى |
|---|---|---|
| Template 1 exact value | «لو الـ target موجود، فهو في [lo, hi]» | لما الـ range يفضى (lo > hi)، لأن الـ target ممكن ما يكونش موجود أصلًا. |
| Template 2 first true | «أول T موجود أكيد في [lo, hi]» | لما يفضل مرشّح واحد (lo === hi)، لأن الإجابة مضمونة، فاللي فاضل هو هي. |
الفرق ده هو اللي بيحدد <= ولا <، مش ذوق ومش حفظ.
يلا نطبّق الجملة دي على أبسط مسألة: دوّر على رقم في array مترتبة.
Template 1: دوّر على قيمة بالظبط (مثال محلول 1: Binary Search)
array مترتبة تصاعدي وكل أرقامها مختلفة، ورقم target. رجّع الـ index بتاعه، ولو مش موجود رجّع -1. المسألة طالبة O(log n).
نفكّر فيها مع بعض
- Brute force: linear search،
O(n). بس المسألة قالتO(log n)صريح، وده signal مباشر لـ binary search. - الـ key insight: قارن بالعنصر اللي في النص. لو أصغر من الـ target، النص الشمال كله أصغر، ارميه. لو أكبر، ارمي اليمين.
- الخطة: الـ invariant اللي فوق بالحرف: ابدأ بالـ array كلها، وصغّر الـ range لحد ما تلاقيه أو الـ range يفضى.
- Edge cases: عنصر واحد، array فاضية، الـ target أصغر أو أكبر من الكل، أو أول أو آخر عنصر.
- شغالة بس لو الـ array مترتبة. من غير ترتيب، مقارنة
nums[mid]بالـ target ما بتقولش أي حاجة عن الناحيتين. lo = 0: أول خانة ممكن الـ target يكون فيها.length - 1مشlength، لأنhiداخل في الـ range وآخر خانة هيn - 1. لو كتبتlength، الـmidممكن يوصل لـnوتقراnums[n] = undefined.<=مش<، لأن لماlo === hiفيه خانة لسه ما اتبصّش عليها. بـ<، الـ input[5]و target = 5 هيرجّع-1والـ 5 قدامك.- في JS القسمة مش بتقطع الكسر زي C++:
(0 + 5) / 2 = 2.5وnums[2.5]بـundefined. الـMath.floorبيقرّب لتحت، وفي Template 2 هيبقى إجباري. - لقيناه، فـ early return.
===مش==عشان ما يحصلش type coercion. nums[mid]أصغر، فـmidوالشمال كله out مرة واحدة. والـ+ 1لأنmidنفسه اتبص عليه وطلع مش هو. لو سبته جوه، الـ range ممكن ما يصغرش خالص (الجزء الجاي).- نفس المنطق بالعكس. والـ
elseمعناها «أكبر» بالظبط، لأن «يساوي» عمل return في سطر 6. - الـ range فضي، فالـ target مش موجود. وخلي بالك: ساعتها
loبيبقى واقف على المكان اللي الـ target كان هيتحط فيه. هنحتاجها في المثال الجاي.
الـ animation مربوطة بالكود: السطر اللي بيتنفّذ بيتلوّن، والخانات اللي اترمت بتبهت. ركّز إن كل خطوة بترمي نص الباقي على الأقل:
ولما الرقم مش موجود، شوف lo و hi بيقرّبوا لحد ما يعدّوا بعض. ده بالظبط معنى «الـ range فضي»:
| Input | target | المتوقع | ليه الحالة دي مهمة |
|---|---|---|---|
| [5] | 5 | 0 | lo = hi = 0، ومن غير <= هتطلع -1 |
| [] | 3 | -1 | hi = -1 من الأول، والـ loop مش بتدخل |
| [1, 4, ..., 30] | 1 | 0 | أول عنصر: hi بينزل لحد lo |
| [1, 4, ..., 30] | 30 | 9 | آخر عنصر: lo بيطلع لحد hi |
| [1, 4, ..., 30] | 31 | -1 | أكبر من الكل: lo بيوصل n = 10 |
Complexity: كل لفة بترمي نص الـ range على الأقل، فـ O(log n) time و O(1) space.
طب ليه mid + 1 مش mid؟ ما هو mid مش الإجابة كده كده، يعني مش هتضيع حاجة. الجزء الجاي هيوريك بيحصل إيه.
ليه mid + 1 و mid - 1؟ شوف الـ infinite loop بعينك
صح، الإجابة مش هتضيع لو كتبت lo = mid، والـ invariant لسه صح. المشكلة إن الـ range ممكن ما يصغرش. خد نفس الكود من غير الـ ± 1، وشغّله مرتين على [1, 3, 5, 7]: مرة بندوّر على 6، ومرة على 0 (الاتنين مش موجودين):
الـ animation وقفت لأننا وقّفناها، بس الكود الحقيقي هيلف للأبد والـ judge هيديك TLE. السبب:
- range فيه خانتين
[2, 3]: الـmid = floor(5 / 2) = 2 = lo، وlo = midبيرجّع نفس الـ range. - range فيه خانة واحدة
[0, 0]: الـmid = 0، وhi = midبيسيبhi = 0، والشرط0 <= 0لسه true.
± 1 بيضمن إن mid نفسه بيخرج كل لفة.
الـ mid الآمن
- في C++ و Java الـ
intبيقف عند حوالي 2.1 مليار، فـlo + hiممكن يعمل overflow ويقلب سالب. عشان كده بيكتبواlo + (hi - lo) / 2. لو بتحل بـ C++، اكتبها كده. - في JS الأرقام doubles ومضمونة لحد
2⁵³، فـlo + hiمش هيعمل overflow في أي مسألة. بس(lo + hi) >> 1فخ: الـ>>بيحوّل لـ 32-bit الأول، و(2e9 + 2e9) >> 1بتطلع-147483648. خليك علىMath.floor. floorمشMath.trunc: للأرقام السالبةMath.trunc(-0.5) = 0(بيقرّب لفوق)، وده ممكن يعلّق Template 2 اللي محتاج mid يقرّب لتحت دايمًا.
Template 1 بيرجّع -1 لو الرقم مش موجود. طب لو عايز المكان اللي المفروض يتحط فيه؟
Template 2: أول true (مثال محلول 2: Search Insert Position)
array مترتبة بأرقام مختلفة، ورقم target. لو موجود رجّع مكانه. لو مش موجود، رجّع المكان اللي لو حطيته فيه الـ array تفضل مترتبة. في O(log n).
الجديد هنا إن إحنا مش بندوّر على قيمة بالظبط، إحنا بندوّر على أول خانة بتحقق شرط. ودي هتبقى أهم template في الفصل.
نفكّر فيها مع بعض
- افهم المطلوب: في الحالتين، الإجابة هي أول index قيمته
>= target. لو موجود، أول رقم>=هو نفسه. لو مش موجود، أول رقم أكبر منه هو مكانه. - Brute force: امشي لحد أول رقم
>= target،O(n). - الـ key insight: السؤال «
nums[i] >= target؟» شكلهF F F T T T، وعايزين أول T. - الإجابة ممكن تبقى
nلو الـ target أكبر من الكل (مفيش ولا T). فالـ range لازم يشملn:hi = n.
فاكر إن lo في Template 1 بيقف على مكان الإضافة؟ كان هيحل المسألة دي. بس هنكتبها بـ Template 2 لأنه هو اللي هيحل كل مسائل «أول مكان» الجاية.
lo = 0: أصغر إجابة ممكنة.lengthمش- 1: الـ invariant هنا «الإجابة أكيد في[lo, hi]»، والإجابة ممكن تبقىn. بـn - 1، الـ input[1, 3]و target = 5 هيرجّع 1 بدل 2. ومش هنقراnums[n]أبدًا، لأنmid < hiدايمًا.<مش<=: لماlo === hiفاضل مرشّح واحد، وهو الإجابة، فنقف. بـ<=هيحسبmid = lo، ولو T هيعملhi = midنفس القيمة للأبد.- الـ floor هنا إجباري: بيضمن
mid < hi، فـhi = midلازم يصغّر الـ range. بـceil، عندlo = 2وhi = 3هيطلعmid = 3 = hi: infinite loop. - السؤال: هل
midفي منطقة الـ T؟ hi = midمشmid - 1: الـmidطلع T، يعني ممكن يكون هو أول T. في[2, 4, 6, 8, 10, 12]و target = 8، أولmidهو الإجابة نفسها، وhi = mid - 1هيخلّي الكود يرجّع 2 بدل 3.- الـ
midطلع F، فلا هو ولا اللي شماله ممكن يكونوا أول T. فـmid + 1بأمان، وده كمان اللي بيصغّر الـ range لماmid = lo. lo === hiهو أول T. ولو مفيش T خالص،loبيوصلn، وده مكان الإضافة في الآخر من غير أيifزيادة.
الصف التاني في الـ animation هو إجابة nums[i] >= target على كل خانة. الخانة الفاضية في آخر الصف الأول هي index n (برا الـ array)، حطيناها عشان hi يبان، واعتبرها T. الكود بيتشغّل مرتين: target = 7، وبعدين 13.
| Input | target | المتوقع | ليه الحالة دي مهمة |
|---|---|---|---|
| [] | 5 | 0 | hi = 0 من الأول، والـ loop مش بتدخل |
| [2, 4, 6, 8, 10, 12] | 1 | 0 | lo بيفضل 0، و hi بينزل له |
| [2, 4, 6, 8, 10, 12] | 13 | 6 | الإجابة n: ده سبب hi = n |
| [1, 3] | 5 | 2 | بـ hi = n - 1 كانت هتطلع 1 |
Complexity: O(log n) time و O(1) space.
std::lower_bound في C++ و bisect_left في Python). وأختها upper bound هي نفس الكود بشرط nums[mid] > target، بترجّع أول رقم أكبر من الـ target.
lower bound بيدّيك أول ظهور للرقم. طب لو الرقم متكرر وعايز آخر ظهور كمان؟
مثال محلول 3: First and Last Position
array مترتبة وممكن فيها تكرار، ورقم target. رجّع أول وآخر index الـ target ظهر فيهم، أو [-1, -1] لو مش موجود. في O(log n).
الجديد هنا إن مش هنكتب binary search جديد خالص. هنستخدم lower bound مرتين، ونتأكد إن الرقم موجود أصلًا.
نفكّر فيها مع بعض
- حل شكله ذكي بس مش هو: Template 1 يلاقي أي 8، وبعدين نتوسّع شمال ويمين. لو الـ array كلها 8، التوسّع ده
O(n)، والـ interviewer هيسألك عليه بالظبط. - الـ key insight: أول 8 = أول index
>= 8. وآخر 8 = (أول index>= 9) ناقص 1، لأن أول رقم أكبر من 8، اللي قبله على طول هو آخر 8. - Edge cases: lower bound بيرجّع رقم دايمًا، حتى لو الـ target مش موجود. فلازم نشيك الخانة دي. وكمان: array فاضية، أو كلها نفس الرقم.
- أول index
>= target. لو الـ target موجود، ده أول ظهور. first === nمعناها كل الأرقام أصغر. وnums[first] !== targetمعناها أول رقم>=طلع أكبر (لو الـ target 6، هيقف على 7). الـ||بيقف عند أول true، فالشرط الأول بيحمي التاني من قراءةnums[n].- ليه
target + 1؟ الأرقام integers، فأول رقم>= 9هو أول رقم أكبر من 8. لو الأرقام كسور، الحيلة دي مش هتنفع، اكتب upper bound بشرط>. - مش محتاجين نشيك
last: طالماfirstموجود، يبقىlast >= firstأكيد. - Template 2 بالحرف، اتكتب مرة واحدة واستخدمناه مرتين. أنضف وأقل في الغلط من اتنين binary search بشروط مختلفة شوية.
| Input | target | المتوقع | ليه الحالة دي مهمة |
|---|---|---|---|
| [5, 7, 7, 8, 8, 8, 10] | 6 | [-1, -1] | first = 1 بس nums[1] = 7 |
| [5, 7, 7, 8, 8, 8, 10] | 11 | [-1, -1] | first = n: الشرط الأول بيحمي |
| [2, 2, 2] | 2 | [0, 2] | الـ array كلها الـ target، وبرضه O(log n) |
| [5, 7, 7, 8, 8, 8, 10] | 10 | [6, 6] | آخر عنصر: lowerBound(11) = 7 = n |
Complexity: اتنين binary search، فـ O(log n) time و O(1) space.
O(n) في الـ worst case لو كله 8، فهعمل lower bound مرتين». الجملة دي بتوريه إنك فاهم الـ complexity مش حافظ.
كده عندك template لقيمة بالظبط وtemplate لأول true، وفيه تالت هنحتاجه قدام. إمتى تستخدم أنهي واحد؟
أنهي template إمتى؟
الفرق بين التلاتة في معنى الـ range، وكل الباقي بيطلع منه. التالت اسمه last true، وهو المراية بتاعة first true، وهنستخدمه في Sqrt(x).
| Template 1 exact value | Template 2 first true | Template 3 last true | |
|---|---|---|---|
| شكل السؤال | موجود ولا لأ؟ | F F F T T T | T T T F F F |
| الـ invariant | لو موجود، فهو في [lo, hi] | أول T أكيد في [lo, hi] | آخر T أكيد في [lo, hi] |
| البداية | lo = 0, hi = n - 1 | lo = 0, hi = n | أصغر وأكبر إجابة ممكنة |
| الشرط | lo <= hi | lo < hi | lo < hi |
| الـ mid | floor (أو ceil، مش فارقة) | floor لازم | ceil لازم |
| التحديث | lo = mid + 1 / hi = mid - 1 | hi = mid / lo = mid + 1 | lo = mid / hi = mid - 1 |
| بيرجّع | mid أو -1 | lo | lo |
| استخدمه في | 704، 74، 33، 374 | 35، 34، 278، 153، 875، 1011 | 69، آخر ظهور، أكبر قيمة تنفع |
= mid من غير ± 1. لو hi = mid، الـ mid لازم عمره ما يساوي hi، فـ floor. لو lo = mid، الـ mid لازم عمره ما يساوي lo، فـ ceil. باختصار: «lo = mid» يبقى ceil.
ولو مش عايز تحفظ Template 3: «آخر T» = «أول F ناقص 1»، فتقلب السؤال وتستخدم Template 2. الاتنين صح، بس ما تخلطش: lo < hi مع hi = mid - 1، أو lo <= hi مع hi = mid، دي توليفات بتعلّق أو بتضيّع الإجابة.
لحد دلوقتي الـ array كانت مترتبة من أولها لآخرها. طب لو حد لفّها؟
مثال محلول 4: Rotated Sorted Array (153 و 33)
array مترتبة اتلفّت: حتة من آخرها اتنقلت لأولها، يعني [1, 2, 3, 5, 6, 7, 8, 9] بقت [5, 6, 7, 8, 9, 1, 2, 3]. هي حتتين مترتبين ورا بعض، وفيه «وقعة» واحدة بس (من 9 لـ 1). والـ key insight: أي mid بيقسمها نصين، واحد منهم على الأقل مترتب، لأن وقعة واحدة ما تقدرش تبقى في النصين.
array مترتبة واتلفّت عدد مرات مش معروف (ممكن صفر)، وأرقامها مختلفة. رجّع أصغر رقم فيها، في O(log n).
الجديد هنا إن السؤال اللي بيتقلب مش «>= target؟». مفيش target أصلًا، والسؤال هو «إنت في الحتة التانية؟».
نفكّر فيها مع بعض
- Brute force:
Math.min(...nums)،O(n). - السؤال اللي بيتقلب: «
nums[i] <=آخر رقم؟». الحتة الأولى كلها أكبر من آخر رقم (F)، والتانية كلها أصغر منه أو تساويه (T). أول T هو الـ min، يعني Template 2. - في الكود بنقارن بـ
nums[hi]بدل آخر رقم، ونفس النتيجة، لأنhiعمره ما بيخرج من الحتة التانية. - ليه مش
nums[lo]؟ في[1, 2, 3, 4, 5](مش ملفوفة)،nums[mid] > nums[lo]هتبعدك يمين، والكود هيرجّع 4.
hi = n - 1مشn، لأن الـ min أكيد جوه الـ array. الـ range المهم يكون فيه الإجابة، مش أكتر.nums[mid] > nums[hi]: رقم أكبر من حاجة على يمينه، يبقى الوقعة بينmidوhi، وmidفي الحتة الكبيرة. فهو مش الـ min:mid + 1.- غير كده، من
midلـhiمترتب، والـ min هوmidأو شماله.hi = midمشmid - 1، لأنmidنفسه ممكن يكون هو. - بنرجّع القيمة مش الـ index. اقرا المسألة كويس.
الصف التاني هو السؤال اللي بيتقلب: «nums[i] <= 3؟» (3 آخر رقم):
Complexity: O(log n) time و O(1) space.
نفس النوع من الـ arrays، ورقم target. رجّع الـ index بتاعه أو -1، في O(log n).
الجديد هنا إن قبل ما ترمي نص، لازم تعرف الأول أنهي نص مترتب، وتسأل السؤال جوه النص ده بس.
نفكّر فيها مع بعض
- حل من خطوتين: لاقي الـ min بالكود اللي فوق، وبعدين Template 1 على الحتة الصح. صح و
O(log n)، قوله لو اتزنقت. بس فيه حل بلفة واحدة. - الـ key insight: في النص المترتب تقدر تسأل سؤال أكيد: «الـ target بين أوله وآخره؟». لو آه، روح له. لو لأ، يبقى في النص التاني.
- أنهي نص مترتب؟ لو
nums[lo] <= nums[mid]، الشمال مفيهوش وقعة. غير كده، اليمين هو المترتب. - Edge cases: عنصر واحد، array مش ملفوفة، و
[3, 1].
- Template 1 بالظبط (range مقفول،
<=، و floor)، لأننا بندوّر على قيمة ممكن ما تكونش موجودة. <=مش<: لماlo === mid، النص الشمال خانة واحدة، وده مترتب طبعًا. بـ<، الـ input[3, 1]و target = 1 هيرجّع-1.- الـ target جوه الشمال لو
nums[lo] <= target < nums[mid].<=عندloلأنه ممكن يكون هو، و<عندmidلأن سطر 5 استبعده. - مش في الشمال المترتب، يبقى في اليمين لو موجود. اليمين ممكن يكون فيه الوقعة، ومش فارقة، اللفة الجاية هتتعامل معاه.
- نفس الفكرة للنص اليمين المترتب: جواه لو
nums[mid] < target <= nums[hi]، غير كده في الشمال.
الخانات الزرقا هي النص المترتب اللي اكتشفناه في الخطوة دي:
| Input | target | المتوقع | ليه الحالة دي مهمة |
|---|---|---|---|
| [3, 1] | 1 | 1 | lo === mid: لازم <= في سطر 6 |
| [1, 2, 3, 4, 5] | 4 | 3 | مش ملفوفة: الشمال دايمًا مترتب، فبيشتغل زي 704 |
| [5, 6, 7, 8, 9, 1, 2, 3] | 5 | 0 | الـ target هو nums[lo]: لازم <= في سطر 7 |
| [5, 6, 7, 8, 9, 1, 2, 3] | 4 | -1 | مش موجود، والـ range بيفضى |
Complexity: O(log n) time و O(1) space.
nums[lo] === nums[mid] === nums[hi] وما تعرفش أنهي نص مترتب. الحل ساعتها hi--، والـ worst case بيبقى O(n).
في كل اللي فات كان عندنا array بندوّر جواها. طب لو مفيش array مترتبة خالص، والمطلوب رقم؟
Binary search على الإجابة (مثال محلول 5: Koko Eating Bananas)
هنا الحتة اللي بتفرق بين اللي حافظ binary search واللي فاهمه. ساعات المسألة مفيهاش array مترتبة، بس بتسألك عن أصغر رقم (أو أكبر رقم) يحقق حاجة. لو قدرت تكتب ok(x) بترد آه أو لأ، ولو x نفع يبقى أي رقم أكبر منه ينفع، يبقى عندك F F F T T T على الأرقام نفسها.
الجديد هنا إن الـ search space مش indices خالص، ده كل الإجابات الممكنة.
- الإجابة رقم إيه؟ سرعة، حمولة، عدد أيام...
loوhi: أصغر وأكبر قيمة ممكنة، والإجابة لازم تكون جوههم أكيد.ok(x): «لو الإجابةx، أقدر أعمل المطلوب؟». غالبًا loop بسيطةO(n).- monotonic؟ لو
xنفع،x + 1لازم ينفع. - Template 2 على
[lo, hi]، و complexityO(n × log(range)).
عندك كومات موز piles[i]، ومعاك h ساعة. كل ساعة بتختار كومة واحدة وتاكل منها k موزة بالكتير. لو الكومة فيها أقل من k، بتخلّصها وتقعد باقي الساعة (مش بتنقل لكومة تانية). رجّع أقل k تخلّص بيها كل الموز في h ساعة أو أقل.
نفكّر فيها مع بعض
- الـ range: أصغر
kممكن 1، وأكبرkمحتاجينهmax(piles)، لأن بيها كل كومة بتخلص في ساعة، وأي سرعة أكبر مش هتفرق. ok(k): الكومةpمحتاجةceil(p / k)ساعة. نجمع، ولو المجموع<= hيبقى نفعت.- monotonic: لو
kنفعت،k + 1أسرع فأكيد تنفع. يبقى عايزين أول T. - Brute force: جرّب
k = 1, 2, 3.... معmax = 10⁹وn = 10⁴ده10¹³. binary search: حوالي 30 تجربة ×10⁴.
lo = 1مش 0: سرعة 0 ملهاش معنى، وp / 0في JS بتطلعInfinityمن غير error. وMath.max(...piles)تمام معn <= 10⁴، بس مع مئات الآلاف استخدمreduce.- Template 2:
maxبتنفع دايمًا (المسألة ضامنةh >= piles.length)، فالإجابة مضمونة في الـ range. kنفعت، بس ممكن تكون هي الإجابة:hi = kمشk - 1.kما نفعتش، وأي أبطأ منها مش هتنفع:lo = k + 1.Math.ceilمشfloor: كومة 7 بسرعة 4 محتاجة ساعتين، مش1.75ولا 1. بـ floor هتقلّل الساعات، والكود هيرجّع 3 بدل 4.
الصف الأول هو الـ search space: كل السرعات من 1 لـ 11، والـ pointers واقفين على سرعات مش indices. والصف التالت هو ساعات كل كومة بالسرعة اللي بنجرّبها:
Complexity: log₂(max) تجربة، كل واحدة O(n)، يعني O(n log M) و M هنا max(piles). مع M = 10⁹ ده حوالي 30n، و O(1) space.
في Koko الـ ok() كانت مجموع بسيط. طب لو الـ ok() نفسها محتاجة simulation؟
مثال محلول 6: Capacity To Ship Packages
شحنات بأوزان weights لازم تتشحن بنفس الترتيب في days يوم. كل يوم المركب بتحمّل شحنات ورا بعض من غير ما الحمولة تعدّي الـ capacity. رجّع أقل capacity تخلّص في days يوم.
الجديد هنا إن ok(cap) عبارة عن simulation بـ greedy، وإن اختيار lo غلط مش بس بيبطّأ، ده بيبوّظ الإجابة.
نفكّر فيها مع بعض
- نفس شكل Koko: «أقل حاجة تكفي». أول ما تسمعها فكّر في binary search على الإجابة.
- الـ range: أقل capacity = أتقل شحنة (أقل من كده مش هتطلع المركب). أكبر = مجموع الأوزان (كله في يوم).
ok(cap): نحمّل بالترتيب، ولما الشحنة الجاية تعدّي الحمولة نبدأ يوم جديد. الـ greedy ده صح لأن إنك تحمّل أكتر النهارده عمره ما بيأخرك.- monotonic: capacity أكبر يبقى أيام أقل أو زي ما هي.
lo = maxمش 1:daysNeededمش بتشيك إن شحنة لوحدها أتقل من الـ cap، فلو بدأت من 1 هتقبل capacities مستحيلة.[1, 10]و days = 2 بـlo = 1بترجّع 1، والصح 10.reduceبيجمع الأوزان، والـ0هي القيمة المبدئية. بالحمولة دي يوم واحد بيكفي، فالإجابة مضمونة.- Template 2 بالحرف:
hi = capلو نفعت، وlo = cap + 1لو لأ. d = 1لأننا بنبدأ في أول يوم. بـ 0 كل الإجابات هتطلع ناقصة يوم.>مش>=: لو الحمولة هتبقى بالظبط قد الـ cap، الشحنة تطلع عادي.
الصف الأول هو كل الـ capacities الممكنة (من 3 لـ 10). وفي الصف التاني، كل لون يوم شحن بالـ capacity اللي بنجرّبها:
Complexity: O(n log S) و S هنا مجموع الأوزان، و O(1) space.
كل اللي فات كان «أصغر رقم ينفع» (أول T). طب لو المطلوب أكبر رقم ينفع؟
مثال محلول 7: Sqrt(x) و Template 3 (last true)
رقم x >= 0. رجّع الجذر التربيعي بتاعه مقرّب لتحت (integer)، من غير Math.sqrt ولا ** 0.5.
الجديد هنا إن عايزين آخر T مش أول T، وده بيقلب الـ floor لـ ceil.
نفكّر فيها مع بعض
- الإجابة بالكلام: أكبر
kفيهk * k <= x. - شكل السؤال: «
k * k <= x؟» بيطلعT T T F F F، وعايزين آخر T: Template 3. - الـ range:
[0, x]، والـ 0 دايمًا T، فالإجابة مضمونة. - طريقة تانية: أول
kفيهk * k > x(Template 2)، والإجابة قبله بواحد.
lo = 0عشانx = 0، وhi = xعشانx = 1. كده مفيش أيifللحالات الصغيرة.- زي Template 2: الإجابة مضمونة، فنقف لما يفضل مرشّح واحد.
- ليه
ceil؟ الفرع اللي فيه= midهوlo = mid. بـ floor، عندlo = 2وhi = 3هيطلعmid = 2 = lo، ولو نفعloهيفضل 2 للأبد. midنفع، فالإجابة هو أو أكبر. في C++ الـmid * midبيعمل overflow فيintبعد 46340 (استخدمlong long)، في JS تمام لحد2⁵³.midمربعه أكبر منx، فهو وكل اللي أكبر منه out:hi = mid - 1.
Complexity: O(log x)، يعني حوالي 31 لفة لأكبر input، و O(1) space.
كده خلصنا الأمثلة. الجزء الجاي فيه الغلطات اللي الكل بيقع فيها، عشان تشوفها قبل ما تقع فيها.
غلطات مشهورة
binary search كوده قصير، وده اللي بيخلّي الغلط فيه سهل. كل غلطة هنا بتطلّع Wrong Answer أو TLE.
1. lo < hi مع Template 1
الـ range مقفول، فلما lo === hi لسه فيه خانة. يا lo <= hi مع hi = n - 1، يا Template 2 كله. ما تاخدش نص من ده ونص من ده.
2. نسيت الـ ± 1
في Template 1 الـ mid اتبص عليه، فلازم يخرج من الـ range في الفرعين.
3. hi = mid - 1 في Template 2
لما mid يطلع T، ممكن يكون هو الإجابة. سيبه: hi = mid.
4. hi = nums.length - 1 لما الإجابة ممكن تبقى n
في Search Insert، لو الـ target أكبر من الكل الإجابة n، و [1, 3] مع target = 5 هترجّع 1 بدل 2. القاعدة: الـ range لازم يشمل كل إجابة ممكنة، حتى لو برا الـ array.
5. mid غلط: من غير floor، أو بـ >> 1
Math.floor((lo + hi) / 2) دايمًا، و Math.ceil بس في Template 3.
6. الـ range أو ok() غلط
في binary search على الإجابة، الـ template نادرًا ما بيغلط. الغلط بيبقى في الـ range أو في ok. اختبر ok لوحدها على المثال بإيدك قبل ما تحطها في الـ loop.
شفت الغلطات. جرّب نفسك بقى قبل ما تروح LeetCode.
اختبر نفسك
array مترتبة فيها مليون رقم. binary search هيعمل حوالي كام مقارنة في الـ worst case؟
- 1,000
- 500,000
- 20
- 1
كل مقارنة بتقسم الباقي على 2، و 2²⁰ ≈ 1,000,000.
في Search Insert Position، ليه hi = nums.length مش nums.length - 1؟
- عشان الـ indices في JS بتبدأ من 1
- عشان الإجابة ممكن تبقى
n، والـ range لازم يشمل كل إجابة ممكنة - عشان نقرا
nums[n] - مش فارقة، الاتنين صح
الـ invariant في Template 2 إن الإجابة أكيد في [lo, hi]. ومش هنقرا nums[n] أبدًا، لأن الـ floor بيخلي mid < hi.
كتبت Template 2 بس استخدمت Math.ceil للـ mid. إيه اللي هيحصل؟
- هيشتغل عادي
- هيرجّع الإجابة ناقص 1
- ممكن يعلّق في infinite loop لما الـ range يبقى خانتين والـ mid يطلع T
- هيقرا برا الـ array بس
عند lo = 2 و hi = 3، الـ ceil بيدّي mid = 3 = hi، ولو T يبقى hi = 3 تاني للأبد.
في Koko، ليه lo = 1 مش 0؟
- عشان الـ binary search ما بيشتغلش على 0
- عشان سرعة 0 ملهاش معنى، و
p / 0بتطلعInfinityفالحساب بيبوظ بصمت - عشان الإجابة دايمًا أكبر من 1
- مش فارقة
كل قيمة جوه الـ range لازم يكون ليها معنى، لأن الـ binary search ممكن يجرّبها.
في Find Minimum in Rotated Sorted Array، ليه بنقارن بـ nums[hi] مش بـ nums[lo]؟
- عشان أسرع
- الاتنين صح دايمًا
- عشان المقارنة بـ
loبتغلط لو الـ array مش ملفوفة خالص - عشان
nums[lo]ممكن تبقىundefined
في [1, 2, 3, 4, 5]، nums[mid] > nums[lo] true دايمًا، فهتروح يمين وهترجّع 4.
أنهي توليفة من دول صح؟
while (lo <= hi)معhi = midwhile (lo < hi)معhi = mid - 1وlo = mid + 1عشان تلاقي أول Twhile (lo < hi)معmid = ceilوlo = midوhi = mid - 1while (lo < hi)معmid = floorوlo = mid
التالتة هي Template 3. الأولى بتعلّق لما lo === hi، والتانية بترمي أول T لما يبقى هو الـ mid، والرابعة بتعلّق لما mid = lo.
تمرين: فكّر قبل ما تفتح
matrix فيها m صف و n عمود. كل صف مترتب، وأول رقم في كل صف أكبر من آخر رقم في اللي قبله. هل الـ target موجود؟ في O(log(m × n)).
تلميح 1
لو قريت الـ matrix صف ورا صف، هتطلع array واحدة مترتبة طولها m × n. اعمل binary search عليها من غير ما تعملها فعلًا.
تلميح 2
الـ index i في الـ array الوهمية: الصف Math.floor(i / n) والعمود i % n. والباقي Template 1 عادي.
الحل
القسمة على n (عدد الأعمدة) مش m، لأن كل صف فيه n عنصر. والـ complexity O(log(m × n)) و O(1) space.
لو حليت التمرين ده لوحدك، إنت جاهز لـ LeetCode. بالترتيب ده:
اتمرن على LeetCode بالترتيب
كل مسألة بتضيف فكرة واحدة جديدة. قبل أي كود، اكتب كومنت: «الـ range معناه إيه؟». ولو قعدت أكتر من 25 دقيقة، ارجع للـ template بتاعها هنا وبعدين حاول تاني من غير ما تبص.
- Binary SearchTemplate 1 من دماغك لحد ما يطلع من غير تفكير.
- Guess Number Higher or Lowerلعبة التخمين نفسها: الـ range أرقام من 1 لـ n مش array.
- Search Insert PositionTemplate 2: أول T، و
hi = n. - First Bad Versionfirst true في أنقى صورة.
- Sqrt(x)Template 3 و ceil. وجرّبها بـ Template 2 كمان.
- Find Smallest Letter Greater Than Targetupper bound (شرط
>)، ولو مفيش ارجع لأول حرف. - Find First and Last Positionlower bound مرتين.
- Search a 2D Matrixarray وهمية و
i / nوi % n. - Find Minimum in Rotated Sorted Arrayfirst true بسؤال مش واضح: قارن بـ
nums[hi]. - Search in Rotated Sorted Arrayلاقي النص المترتب الأول، وخلي بالك من
nums[lo] <= nums[mid]. - Find Peak Elementمفيش ترتيب خالص: قارن
nums[mid]بـnums[mid + 1]، لو طالع فيه قمة على اليمين أكيد. - Koko Eating Bananasأول binary search على الإجابة. اختبر
ok(k)لوحدها. - Capacity To Ship Packages Within D Daysنفس الفكرة بـ simulation، و
lo = maxمش 1. - Split Array Largest Sumاختياري: هي Ship باسم تاني. لو عرفت ده لوحدك يبقى فهمت الـ pattern.
وفي الآخر، الفصل كله في صفحة واحدة.
الخلاصة
[lo, hi] معناه إيه. الشرط، والتحديث، والبداية، والـ floor ولا ceil، كلهم بيطلعوا من الجملة دي، وكل فرع لازم يصغّر الـ range.
| السؤال | الإجابة |
|---|---|
<= ولا <؟ | <= لو الإجابة ممكن ما تكونش موجودة (Template 1). < لو مضمونة في الـ range. |
hi = n - 1 ولا n؟ | الـ range لازم يشمل كل إجابة ممكنة، ولو ممكن تبقى «بعد الآخر» يبقى n. |
hi = mid ولا mid - 1؟ | لو mid ممكن يكون الإجابة، سيبه. لو اتأكدت إنه مش هو، mid - 1. |
| floor ولا ceil؟ | floor دايمًا، إلا لو عندك lo = mid. |
| إمتى على الإجابة؟ | «أقل / أكبر رقم ينفع»، و ok(x) بتتقلب مرة واحدة. |
| Complexity؟ | O(log n) على array، و O(cost(ok) × log(range)) على الإجابة. |
الفصل الجاي: كده خلصنا الـ Sorting و Searching. في Stack و Monotonic Stack هنبدأ أول data structure خطية بقواعد: آخر حاجة دخلت هي أول حاجة تطلع. وهتشوف إزاي الـ stack بيحل «أول رقم أكبر مني على اليمين» في O(n) بدل O(n²). وفكرة «ارمي نص الاحتمالات» هترجعلك في Binary Search Tree: كل node بتقولك روح شمال ولا يمين، بالظبط زي mid.