Binary Searchlo · mid · hi · lower bound · binary search on the answer

في الفصل اللي فات اتعلمنا نرتّب الداتا ونشتغل على intervals. دلوقتي هنقبض تمن الترتيب ده: لو الداتا مترتبة، مش محتاج تبص على كل عنصر. بتبص في النص وترمي نص الـ search space في كل خطوة، فمليون عنصر بيخلصوا في 20 خطوة. والأهم إنك تكتبه صح من أول مرة، من غير off-by-one ولا infinite loop.

قبله: Sorting و Intervals و Big-O بيمهّد لـ: Binary Search Tree

هتطلع من الفصل ده وإنت عارف

  • تقول بالكلام [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 مش على شمالها.

تشبيه صاحبك مفكّر في رقم من 1 لـ 100، وكل ما تخمّن بيقولك «أكبر» أو «أصغر». اللي ما يعرفش بيقول 1، 2، 3. اللي يعرف بيقول 50 الأول، ولو قاله «أكبر» يبقى رمى 50 رقم بسؤال واحد. بعدها 75، وبعدها 62، وفي 7 تخمينات بالكتير بيوصل لأي رقم. ده binary search بالظبط.

نفس الـ array ونفس الـ 25، بس المرة دي بنبص في النص الأول. الخانات اللي اترمت بتبهت:

3 مقارنات بدل 9، والفرق بيكبر بسرعة رهيبة:

nlinear (worst case)binary (worst case)
10104
1,0001,00010
1,000,0001,000,00020
1,000,000,0001,000,000,00030

الـ key insight: كل مقارنة بتقسم الباقي على 2، فالسؤال بقى «أقسم n على 2 كام مرة لحد ما يفضل عنصر واحد؟». الإجابة log₂ n، يعني O(log n) (راجع Big-O لو محتاج). كل ما تضاعف n، binary search بيزيد one step بس.

طب إزاي تعرف من كلام المسألة إنها binary search، حتى لو مفيهاش array مترتبة أصلًا؟

إزاي تعرفه من المسألة

لما تشوف: sorted arrayO(log n)insert positionfirst / last occurrence rotated sorted arrayminimum X such thatmaximum X such that minimize the largestwithin D days / H hourssqrt / perfect square
ومش هو غالبًا لو: unsorted + find a valuecount subarrays with sum klongest substring with condition

آخر 4 إشارات في أول قائمة مفيهمش array مترتبة خالص، ودول اللي بيوقّعوا الناس. binary search مش محتاج array مترتبة، هو محتاج سؤال إجابته بتتقلب مرة واحدة بس من «لأ» لـ «آه». ولو الـ array مش مترتبة ومطلوب تلاقي قيمة، ده شغل hash map.

النوعبتدوّر على إيهالـ templateأشهر مسائل
قيمة بالظبط
exact match
index رقم معين، أو -1Template 1: lo <= hi704، 74، 33
أول مكان بيحقق شرط
lower bound / first true
أول index الشرط فيه trueTemplate 2: lo < hi، hi = mid35، 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، والكود يعلّق أو يفوّت الإجابة. السبب إنهم حافظين الشكل من غير المعنى. الحل إنك تكتب جملة واحدة قبل الكود، وكل سطر يمشي وراها.

الجملة دي اسمها invariant الـ invariant حاجة صح قبل الـ loop، وبتفضل صح بعد كل لفة. في البحث عن قيمة بالظبط هي:
«لو الـ target موجود، يبقى موجود في الخانات من lo لحد hi، والاتنين داخلين.»

من الجملة دي بس هتطلّع كل سطر:

  1. البداية: الـ target ممكن يكون في أي حتة، فـ lo = 0 و hi = n - 1. ليه n - 1؟ عشان hi داخل في الـ range، وآخر خانة موجودة هي n - 1.
  2. نكمّل لحد إمتى؟ طول ما الـ range فيه خانة واحدة على الأقل. لو lo = hi = 3 فيه خانة لسه ما اتبصّش عليها، فالشرط lo <= hi. والـ range بيفضى لما lo > hi.
  3. nums[mid] < target؟ الـ mid وكل اللي شماله أصغر، فالـ target لو موجود فهو في [mid + 1, hi]: lo = mid + 1. والعكس: hi = mid - 1.
  4. الـ 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)

Binary Search

easyLeetCode 704

array مترتبة تصاعدي وكل أرقامها مختلفة، ورقم target. رجّع الـ index بتاعه، ولو مش موجود رجّع -1. المسألة طالبة O(log n).

Input: nums = [1, 4, 7, 9, 12, 15, 18, 21, 25, 30], target = 15 → 5 Input: nums = [1, 4, 7, 9, 12, 15, 18, 21, 25, 30], target = 10 → -1 Input: nums = [5], target = 5 → 0

نفكّر فيها مع بعض

  1. Brute force: linear search، O(n). بس المسألة قالت O(log n) صريح، وده signal مباشر لـ binary search.
  2. الـ key insight: قارن بالعنصر اللي في النص. لو أصغر من الـ target، النص الشمال كله أصغر، ارميه. لو أكبر، ارمي اليمين.
  3. الخطة: الـ invariant اللي فوق بالحرف: ابدأ بالـ array كلها، وصغّر الـ range لحد ما تلاقيه أو الـ range يفضى.
  4. Edge cases: عنصر واحد، array فاضية، الـ target أصغر أو أكبر من الكل، أو أول أو آخر عنصر.
  1. شغالة بس لو الـ array مترتبة. من غير ترتيب، مقارنة nums[mid] بالـ target ما بتقولش أي حاجة عن الناحيتين.
  2. lo = 0: أول خانة ممكن الـ target يكون فيها.
  3. length - 1 مش length، لأن hi داخل في الـ range وآخر خانة هي n - 1. لو كتبت length، الـ mid ممكن يوصل لـ n وتقرا nums[n] = undefined.
  4. <= مش <، لأن لما lo === hi فيه خانة لسه ما اتبصّش عليها. بـ <، الـ input [5] و target = 5 هيرجّع -1 والـ 5 قدامك.
  5. في JS القسمة مش بتقطع الكسر زي C++: (0 + 5) / 2 = 2.5 و nums[2.5] بـ undefined. الـ Math.floor بيقرّب لتحت، وفي Template 2 هيبقى إجباري.
  6. لقيناه، فـ early return. === مش == عشان ما يحصلش type coercion.
  7. nums[mid] أصغر، فـ mid والشمال كله out مرة واحدة. والـ + 1 لأن mid نفسه اتبص عليه وطلع مش هو. لو سبته جوه، الـ range ممكن ما يصغرش خالص (الجزء الجاي).
  8. نفس المنطق بالعكس. والـ else معناها «أكبر» بالظبط، لأن «يساوي» عمل return في سطر 6.
  9. الـ range فضي، فالـ target مش موجود. وخلي بالك: ساعتها lo بيبقى واقف على المكان اللي الـ target كان هيتحط فيه. هنحتاجها في المثال الجاي.

الـ animation مربوطة بالكود: السطر اللي بيتنفّذ بيتلوّن، والخانات اللي اترمت بتبهت. ركّز إن كل خطوة بترمي نص الباقي على الأقل:

ولما الرقم مش موجود، شوف lo و hi بيقرّبوا لحد ما يعدّوا بعض. ده بالظبط معنى «الـ range فضي»:

Inputtargetالمتوقعليه الحالة دي مهمة
[5]50lo = hi = 0، ومن غير <= هتطلع -1
[]3-1hi = -1 من الأول، والـ loop مش بتدخل
[1, 4, ..., 30]10أول عنصر: hi بينزل لحد lo
[1, 4, ..., 30]309آخر عنصر: 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. السبب:

القاعدة الذهبية كل فرع جوه الـ loop لازم يصغّر الـ range. اسأل نفسك عن كل فرع: «لو الـ range فيه خانتين بس، أو خانة واحدة بس، الفرع ده هيصغّره؟». لو لأ، عندك infinite loop مستنيك. الـ ± 1 بيضمن إن mid نفسه بيخرج كل لفة.

الـ mid الآمن

Template 1 بيرجّع -1 لو الرقم مش موجود. طب لو عايز المكان اللي المفروض يتحط فيه؟

Template 2: أول true (مثال محلول 2: Search Insert Position)

Search Insert Position

easyLeetCode 35

array مترتبة بأرقام مختلفة، ورقم target. لو موجود رجّع مكانه. لو مش موجود، رجّع المكان اللي لو حطيته فيه الـ array تفضل مترتبة. في O(log n).

Input: nums = [2, 4, 6, 8, 10, 12], target = 7 → 3 (between 6 and 8) Input: nums = [2, 4, 6, 8, 10, 12], target = 8 → 3 (found) Input: nums = [2, 4, 6, 8, 10, 12], target = 13 → 6 (after everything) Input: nums = [2, 4, 6, 8, 10, 12], target = 1 → 0

الجديد هنا إن إحنا مش بندوّر على قيمة بالظبط، إحنا بندوّر على أول خانة بتحقق شرط. ودي هتبقى أهم template في الفصل.

نفكّر فيها مع بعض

  1. افهم المطلوب: في الحالتين، الإجابة هي أول index قيمته >= target. لو موجود، أول رقم >= هو نفسه. لو مش موجود، أول رقم أكبر منه هو مكانه.
  2. Brute force: امشي لحد أول رقم >= target، O(n).
  3. الـ key insight: السؤال «nums[i] >= target؟» شكله F F F T T T، وعايزين أول T.
  4. الإجابة ممكن تبقى n لو الـ target أكبر من الكل (مفيش ولا T). فالـ range لازم يشمل n: hi = n.

فاكر إن lo في Template 1 بيقف على مكان الإضافة؟ كان هيحل المسألة دي. بس هنكتبها بـ Template 2 لأنه هو اللي هيحل كل مسائل «أول مكان» الجاية.

  1. lo = 0: أصغر إجابة ممكنة.
  2. length مش - 1: الـ invariant هنا «الإجابة أكيد في [lo, hi]»، والإجابة ممكن تبقى n. بـ n - 1، الـ input [1, 3] و target = 5 هيرجّع 1 بدل 2. ومش هنقرا nums[n] أبدًا، لأن mid < hi دايمًا.
  3. < مش <=: لما lo === hi فاضل مرشّح واحد، وهو الإجابة، فنقف. بـ <= هيحسب mid = lo، ولو T هيعمل hi = mid نفس القيمة للأبد.
  4. الـ floor هنا إجباري: بيضمن mid < hi، فـ hi = mid لازم يصغّر الـ range. بـ ceil، عند lo = 2 و hi = 3 هيطلع mid = 3 = hi: infinite loop.
  5. السؤال: هل mid في منطقة الـ T؟
  6. hi = mid مش mid - 1: الـ mid طلع T، يعني ممكن يكون هو أول T. في [2, 4, 6, 8, 10, 12] و target = 8، أول mid هو الإجابة نفسها، و hi = mid - 1 هيخلّي الكود يرجّع 2 بدل 3.
  7. الـ mid طلع F، فلا هو ولا اللي شماله ممكن يكونوا أول T. فـ mid + 1 بأمان، وده كمان اللي بيصغّر الـ range لما mid = lo.
  8. lo === hi هو أول T. ولو مفيش T خالص، lo بيوصل n، وده مكان الإضافة في الآخر من غير أي if زيادة.

الصف التاني في الـ animation هو إجابة nums[i] >= target على كل خانة. الخانة الفاضية في آخر الصف الأول هي index n (برا الـ array)، حطيناها عشان hi يبان، واعتبرها T. الكود بيتشغّل مرتين: target = 7، وبعدين 13.

Inputtargetالمتوقعليه الحالة دي مهمة
[]50hi = 0 من الأول، والـ loop مش بتدخل
[2, 4, 6, 8, 10, 12]10lo بيفضل 0، و hi بينزل له
[2, 4, 6, 8, 10, 12]136الإجابة n: ده سبب hi = n
[1, 3]52بـ hi = n - 1 كانت هتطلع 1

Complexity: O(log n) time و O(1) space.

اسم مفيد في الانترفيو الدالة دي اسمها lower bound (std::lower_bound في C++ و bisect_left في Python). وأختها upper bound هي نفس الكود بشرط nums[mid] > target، بترجّع أول رقم أكبر من الـ target.

lower bound بيدّيك أول ظهور للرقم. طب لو الرقم متكرر وعايز آخر ظهور كمان؟

مثال محلول 3: First and Last Position

Find First and Last Position of Element in Sorted Array

mediumLeetCode 34

array مترتبة وممكن فيها تكرار، ورقم target. رجّع أول وآخر index الـ target ظهر فيهم، أو [-1, -1] لو مش موجود. في O(log n).

Input: nums = [5, 7, 7, 8, 8, 8, 10], target = 8 → [3, 5] Input: nums = [5, 7, 7, 8, 8, 8, 10], target = 6 → [-1, -1] Input: nums = [], target = 0 → [-1, -1]

الجديد هنا إن مش هنكتب binary search جديد خالص. هنستخدم lower bound مرتين، ونتأكد إن الرقم موجود أصلًا.

نفكّر فيها مع بعض

  1. حل شكله ذكي بس مش هو: Template 1 يلاقي أي 8، وبعدين نتوسّع شمال ويمين. لو الـ array كلها 8، التوسّع ده O(n)، والـ interviewer هيسألك عليه بالظبط.
  2. الـ key insight: أول 8 = أول index >= 8. وآخر 8 = (أول index >= 9) ناقص 1، لأن أول رقم أكبر من 8، اللي قبله على طول هو آخر 8.
  3. Edge cases: lower bound بيرجّع رقم دايمًا، حتى لو الـ target مش موجود. فلازم نشيك الخانة دي. وكمان: array فاضية، أو كلها نفس الرقم.
  1. أول index >= target. لو الـ target موجود، ده أول ظهور.
  2. first === n معناها كل الأرقام أصغر. و nums[first] !== target معناها أول رقم >= طلع أكبر (لو الـ target 6، هيقف على 7). الـ || بيقف عند أول true، فالشرط الأول بيحمي التاني من قراءة nums[n].
  3. ليه target + 1؟ الأرقام integers، فأول رقم >= 9 هو أول رقم أكبر من 8. لو الأرقام كسور، الحيلة دي مش هتنفع، اكتب upper bound بشرط >.
  4. مش محتاجين نشيك last: طالما first موجود، يبقى last >= first أكيد.
  5. Template 2 بالحرف، اتكتب مرة واحدة واستخدمناه مرتين. أنضف وأقل في الغلط من اتنين binary search بشروط مختلفة شوية.
Inputtargetالمتوقعليه الحالة دي مهمة
[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.

في الانترفيو لو بدأت بحل «لاقي أي 8 واتوسّع»، قول إنت قبل ما يسألك: «ده 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 TT T T F F F
الـ invariantلو موجود، فهو في [lo, hi]أول T أكيد في [lo, hi]آخر T أكيد في [lo, hi]
البدايةlo = 0, hi = n - 1lo = 0, hi = nأصغر وأكبر إجابة ممكنة
الشرطlo <= hilo < hilo < hi
الـ midfloor (أو ceil، مش فارقة)floor لازمceil لازم
التحديثlo = mid + 1 / hi = mid - 1hi = mid / lo = mid + 1lo = mid / hi = mid - 1
بيرجّعmid أو -1lolo
استخدمه في704، 74، 33، 37435، 34، 278، 153، 875، 101169، آخر ظهور، أكبر قيمة تنفع
إزاي تفتكر floor ولا ceil بص على الفرع اللي فيه = 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 بيقسمها نصين، واحد منهم على الأقل مترتب، لأن وقعة واحدة ما تقدرش تبقى في النصين.

تشبيه ساعة الحيطة: الأرقام من 1 لـ 12 مترتبة، بس لو بدأت تقرا من الـ 5، هتقرا 5، 6، ...، 12، وبعدين 1، 2، 3، 4. أصغر رقم هو المكان اللي الأرقام «وقعت» فيه.

Find Minimum in Rotated Sorted Array

mediumLeetCode 153

array مترتبة واتلفّت عدد مرات مش معروف (ممكن صفر)، وأرقامها مختلفة. رجّع أصغر رقم فيها، في O(log n).

Input: [5, 6, 7, 8, 9, 1, 2, 3] → 1 Input: [1, 2, 3, 4, 5] → 1 (not rotated at all) Input: [2, 1] → 1

الجديد هنا إن السؤال اللي بيتقلب مش «>= target؟». مفيش target أصلًا، والسؤال هو «إنت في الحتة التانية؟».

نفكّر فيها مع بعض

  1. Brute force: Math.min(...nums)، O(n).
  2. السؤال اللي بيتقلب: «nums[i] <= آخر رقم؟». الحتة الأولى كلها أكبر من آخر رقم (F)، والتانية كلها أصغر منه أو تساويه (T). أول T هو الـ min، يعني Template 2.
  3. في الكود بنقارن بـ nums[hi] بدل آخر رقم، ونفس النتيجة، لأن hi عمره ما بيخرج من الحتة التانية.
  4. ليه مش nums[lo]؟ في [1, 2, 3, 4, 5] (مش ملفوفة)، nums[mid] > nums[lo] هتبعدك يمين، والكود هيرجّع 4.
  1. hi = n - 1 مش n، لأن الـ min أكيد جوه الـ array. الـ range المهم يكون فيه الإجابة، مش أكتر.
  2. nums[mid] > nums[hi]: رقم أكبر من حاجة على يمينه، يبقى الوقعة بين mid و hi، و mid في الحتة الكبيرة. فهو مش الـ min: mid + 1.
  3. غير كده، من mid لـ hi مترتب، والـ min هو mid أو شماله. hi = mid مش mid - 1، لأن mid نفسه ممكن يكون هو.
  4. بنرجّع القيمة مش الـ index. اقرا المسألة كويس.

الصف التاني هو السؤال اللي بيتقلب: «nums[i] <= 3؟» (3 آخر رقم):

Complexity: O(log n) time و O(1) space.

Search in Rotated Sorted Array

mediumLeetCode 33

نفس النوع من الـ arrays، ورقم target. رجّع الـ index بتاعه أو -1، في O(log n).

Input: nums = [5, 6, 7, 8, 9, 1, 2, 3], target = 2 → 6 Input: nums = [5, 6, 7, 8, 9, 1, 2, 3], target = 4 → -1 Input: nums = [3, 1], target = 1 → 1

الجديد هنا إن قبل ما ترمي نص، لازم تعرف الأول أنهي نص مترتب، وتسأل السؤال جوه النص ده بس.

نفكّر فيها مع بعض

  1. حل من خطوتين: لاقي الـ min بالكود اللي فوق، وبعدين Template 1 على الحتة الصح. صح و O(log n)، قوله لو اتزنقت. بس فيه حل بلفة واحدة.
  2. الـ key insight: في النص المترتب تقدر تسأل سؤال أكيد: «الـ target بين أوله وآخره؟». لو آه، روح له. لو لأ، يبقى في النص التاني.
  3. أنهي نص مترتب؟ لو nums[lo] <= nums[mid]، الشمال مفيهوش وقعة. غير كده، اليمين هو المترتب.
  4. Edge cases: عنصر واحد، array مش ملفوفة، و [3, 1].
  1. Template 1 بالظبط (range مقفول، <=، و floor)، لأننا بندوّر على قيمة ممكن ما تكونش موجودة.
  2. <= مش <: لما lo === mid، النص الشمال خانة واحدة، وده مترتب طبعًا. بـ <، الـ input [3, 1] و target = 1 هيرجّع -1.
  3. الـ target جوه الشمال لو nums[lo] <= target < nums[mid]. <= عند lo لأنه ممكن يكون هو، و < عند mid لأن سطر 5 استبعده.
  4. مش في الشمال المترتب، يبقى في اليمين لو موجود. اليمين ممكن يكون فيه الوقعة، ومش فارقة، اللفة الجاية هتتعامل معاه.
  5. نفس الفكرة للنص اليمين المترتب: جواه لو nums[mid] < target <= nums[hi]، غير كده في الشمال.

الخانات الزرقا هي النص المترتب اللي اكتشفناه في الخطوة دي:

Inputtargetالمتوقعليه الحالة دي مهمة
[3, 1]11lo === mid: لازم <= في سطر 6
[1, 2, 3, 4, 5]43مش ملفوفة: الشمال دايمًا مترتب، فبيشتغل زي 704
[5, 6, 7, 8, 9, 1, 2, 3]50الـ target هو nums[lo]: لازم <= في سطر 7
[5, 6, 7, 8, 9, 1, 2, 3]4-1مش موجود، والـ range بيفضى

Complexity: O(log n) time و O(1) space.

خلي بالك من التكرار الحلين دول قايمين على إن الأرقام مختلفة. لو فيه تكرار (LeetCode 81 و 154)، ممكن 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 خالص، ده كل الإجابات الممكنة.

تشبيه بتدوّر على أرخص باقة نت تكفيك تتفرج من غير تقطيع. لو 30 ميجا كفاية، أكيد 40 كفاية. ولو 10 مش كفاية، أكيد 5 مش كفاية. فمش هتجرّب كل الباقات: هتجرّب اللي في النص، ولو كفّت تنزل، ولو ما كفّتش تطلع.
  1. الإجابة رقم إيه؟ سرعة، حمولة، عدد أيام...
  2. lo و hi: أصغر وأكبر قيمة ممكنة، والإجابة لازم تكون جوههم أكيد.
  3. ok(x): «لو الإجابة x، أقدر أعمل المطلوب؟». غالبًا loop بسيطة O(n).
  4. monotonic؟ لو x نفع، x + 1 لازم ينفع.
  5. Template 2 على [lo, hi]، و complexity O(n × log(range)).

Koko Eating Bananas

mediumLeetCode 875

عندك كومات موز piles[i]، ومعاك h ساعة. كل ساعة بتختار كومة واحدة وتاكل منها k موزة بالكتير. لو الكومة فيها أقل من k، بتخلّصها وتقعد باقي الساعة (مش بتنقل لكومة تانية). رجّع أقل k تخلّص بيها كل الموز في h ساعة أو أقل.

Input: piles = [3, 6, 7, 11], h = 8 → 4 Input: piles = [30, 11, 23, 4, 20], h = 5 → 30 Input: piles = [30, 11, 23, 4, 20], h = 6 → 23

نفكّر فيها مع بعض

  1. الـ range: أصغر k ممكن 1، وأكبر k محتاجينه max(piles)، لأن بيها كل كومة بتخلص في ساعة، وأي سرعة أكبر مش هتفرق.
  2. ok(k): الكومة p محتاجة ceil(p / k) ساعة. نجمع، ولو المجموع <= h يبقى نفعت.
  3. monotonic: لو k نفعت، k + 1 أسرع فأكيد تنفع. يبقى عايزين أول T.
  4. Brute force: جرّب k = 1, 2, 3.... مع max = 10⁹ و n = 10⁴ ده 10¹³. binary search: حوالي 30 تجربة × 10⁴.
  1. lo = 1 مش 0: سرعة 0 ملهاش معنى، و p / 0 في JS بتطلع Infinity من غير error. و Math.max(...piles) تمام مع n <= 10⁴، بس مع مئات الآلاف استخدم reduce.
  2. Template 2: max بتنفع دايمًا (المسألة ضامنة h >= piles.length)، فالإجابة مضمونة في الـ range.
  3. k نفعت، بس ممكن تكون هي الإجابة: hi = k مش k - 1.
  4. k ما نفعتش، وأي أبطأ منها مش هتنفع: lo = k + 1.
  5. 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

Capacity To Ship Packages Within D Days

mediumLeetCode 1011

شحنات بأوزان weights لازم تتشحن بنفس الترتيب في days يوم. كل يوم المركب بتحمّل شحنات ورا بعض من غير ما الحمولة تعدّي الـ capacity. رجّع أقل capacity تخلّص في days يوم.

Input: weights = [2, 3, 1, 2, 2], days = 3 → 4 (2 | 3, 1 | 2, 2) Input: weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5 → 15 Input: weights = [1, 10], days = 2 → 10

الجديد هنا إن ok(cap) عبارة عن simulation بـ greedy، وإن اختيار lo غلط مش بس بيبطّأ، ده بيبوّظ الإجابة.

نفكّر فيها مع بعض

  1. نفس شكل Koko: «أقل حاجة تكفي». أول ما تسمعها فكّر في binary search على الإجابة.
  2. الـ range: أقل capacity = أتقل شحنة (أقل من كده مش هتطلع المركب). أكبر = مجموع الأوزان (كله في يوم).
  3. ok(cap): نحمّل بالترتيب، ولما الشحنة الجاية تعدّي الحمولة نبدأ يوم جديد. الـ greedy ده صح لأن إنك تحمّل أكتر النهارده عمره ما بيأخرك.
  4. monotonic: capacity أكبر يبقى أيام أقل أو زي ما هي.
  1. lo = max مش 1: daysNeeded مش بتشيك إن شحنة لوحدها أتقل من الـ cap، فلو بدأت من 1 هتقبل capacities مستحيلة. [1, 10] و days = 2 بـ lo = 1 بترجّع 1، والصح 10.
  2. reduce بيجمع الأوزان، والـ 0 هي القيمة المبدئية. بالحمولة دي يوم واحد بيكفي، فالإجابة مضمونة.
  3. Template 2 بالحرف: hi = cap لو نفعت، و lo = cap + 1 لو لأ.
  4. d = 1 لأننا بنبدأ في أول يوم. بـ 0 كل الإجابات هتطلع ناقصة يوم.
  5. > مش >=: لو الحمولة هتبقى بالظبط قد الـ cap، الشحنة تطلع عادي.

الصف الأول هو كل الـ capacities الممكنة (من 3 لـ 10). وفي الصف التاني، كل لون يوم شحن بالـ capacity اللي بنجرّبها:

Complexity: O(n log S) و S هنا مجموع الأوزان، و O(1) space.

نفس المسألة بأسماء تانية LeetCode 410 (قسّم الـ array لـ k حتت وقلّل أكبر مجموع) هي هي بالظبط. ولما تشوف minimize the maximum أو maximize the minimum، ده signal قوي لـ binary search على الإجابة.

كل اللي فات كان «أصغر رقم ينفع» (أول T). طب لو المطلوب أكبر رقم ينفع؟

مثال محلول 7: Sqrt(x) و Template 3 (last true)

Sqrt(x)

easyLeetCode 69

رقم x >= 0. رجّع الجذر التربيعي بتاعه مقرّب لتحت (integer)، من غير Math.sqrt ولا ** 0.5.

Input: x = 8 → 2 (sqrt = 2.828...) Input: x = 16 → 4 Input: x = 0 → 0 Input: x = 1 → 1

الجديد هنا إن عايزين آخر T مش أول T، وده بيقلب الـ floor لـ ceil.

نفكّر فيها مع بعض

  1. الإجابة بالكلام: أكبر k فيه k * k <= x.
  2. شكل السؤال: «k * k <= x؟» بيطلع T T T F F F، وعايزين آخر T: Template 3.
  3. الـ range: [0, x]، والـ 0 دايمًا T، فالإجابة مضمونة.
  4. طريقة تانية: أول k فيه k * k > x (Template 2)، والإجابة قبله بواحد.
  1. lo = 0 عشان x = 0، و hi = x عشان x = 1. كده مفيش أي if للحالات الصغيرة.
  2. زي Template 2: الإجابة مضمونة، فنقف لما يفضل مرشّح واحد.
  3. ليه ceil؟ الفرع اللي فيه = mid هو lo = mid. بـ floor، عند lo = 2 و hi = 3 هيطلع mid = 2 = lo، ولو نفع lo هيفضل 2 للأبد.
  4. mid نفع، فالإجابة هو أو أكبر. في C++ الـ mid * mid بيعمل overflow في int بعد 46340 (استخدم long long)، في JS تمام لحد 2⁵³.
  5. 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 = mid
  • while (lo < hi) مع hi = mid - 1 و lo = mid + 1 عشان تلاقي أول T
  • while (lo < hi) مع mid = ceil و lo = mid و hi = mid - 1
  • while (lo < hi) مع mid = floor و lo = mid

التالتة هي Template 3. الأولى بتعلّق لما lo === hi، والتانية بترمي أول T لما يبقى هو الـ mid، والرابعة بتعلّق لما mid = lo.

تمرين: فكّر قبل ما تفتح

Search a 2D Matrix

mediumLeetCode 74

matrix فيها m صف و n عمود. كل صف مترتب، وأول رقم في كل صف أكبر من آخر رقم في اللي قبله. هل الـ target موجود؟ في O(log(m × n)).

matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]] target = 3 → true target = 13 → false
تلميح 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 search، قول بالكلام [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.