جستوجوی دودویی برای پیدا کردن مرز
آمادگی مصاحبهٔ الگوریتمی با Python
- In 75 minutes, recognize sorted inputs or a false-then-true predicate; reject binary search when this monotone structure cannot be justified.
- Introduce logarithmic halving and a half-open lower-bound template that never indexes outside the array.
- Independently choose the comparisons needed to locate the first and last occurrence of a target.
- Develop Find First and Last Position of Element in Sorted Array from a linear scan to two Python boundary searches.
- Maintain excluded-region invariants, prove strict interval shrinkage, and explain why the final index is the requested boundary.
- Derive O(log n) time and O(1) auxiliary space without slicing or sorting the input.
- Test empty input, absent targets, duplicate-only arrays, and matches at either boundary; diagnose mixed interval conventions and non-progressing updates.
مرزها به شرط یکنواختی
```svg
<svg viewBox="0 0 800 520" xmlns="http://www.w3.org/2000/svg"><text x="400" y="30" text-anchor="middle" font-size="18" class="tm-text" direction="rtl">مرتب صعودی، با تکرار؛ اندیس از صفر؛ ورودی خالی مجاز</text><text x="400" y="63" text-anchor="middle" font-size="17" class="tm-text2">target = 4</text><g font-size="22" text-anchor="middle"><rect x="170" y="85" width="80" height="54" rx="8" class="tm-surface"/><rect x="265" y="85" width="80" height="54" rx="8" class="tm-accent"/><rect x="360" y="85" width="80" height="54" rx="8" class="tm-soft"/><rect x="455" y="85" width="80" height="54" rx="8" class="tm-accent"/><rect x="550" y="85" width="80" height="54" rx="8" class="tm-surface"/><text x="210" y="120" class="tm-text">2</text><text x="305" y="120" class="tm-text">4</text><text x="400" y="120" class="tm-text">4</text><text x="495" y="120" class="tm-text">4</text><text x="590" y="120" class="tm-text">7</text></g><g font-size="15" text-anchor="middle"><text x="210" y="160" class="tm-muted">0</text><text x="305" y="160" class="tm-muted">1</text><text x="400" y="160" class="tm-muted">2</text><text x="495" y="160" class="tm-muted">3</text><text x="590" y="160" class="tm-muted">4</text><text x="305" y="187" class="tm-text-accent" direction="rtl">اولین</text><text x="400" y="187" class="tm-muted" direction="rtl">وسط کافی نیست</text><text x="495" y="187" class="tm-text-accent" direction="rtl">آخرین</text></g><rect x="145" y="210" width="510" height="70" rx="10" class="tm-soft tm-enter"/><text x="400" y="235" text-anchor="middle" font-size="17" class="tm-text">Brute Force: first = −1, last = −1</text><text x="400" y="263" text-anchor="middle" font-size="18" class="tm-text">first: −1 → 1 last: −1 → 1 → 2 → 3</text><text x="400" y="313" text-anchor="middle" font-size="18" class="tm-text" direction="rtl">predicate: عضو حداقل چهار باشد</text><rect x="170" y="329" width="80" height="42" rx="8" class="tm-gold"/><rect x="265" y="329" width="365" height="42" rx="8" class="tm-green tm-enter"/><g text-anchor="middle" font-size="17"><text x="210" y="356" class="tm-text" direction="rtl">غلط</text><text x="305" y="356" class="tm-text" direction="rtl">درست</text><text x="400" y="356" class="tm-text" direction="rtl">درست</text><text x="495" y="356" class="tm-text" direction="rtl">درست</text><text x="590" y="356" class="tm-text" direction="rtl">درست</text></g><text x="400" y="398" text-anchor="middle" font-size="17" class="tm-text-green" direction="rtl">بعد از درست، دیگر غلط نمیشود</text><text x="150" y="449" text-anchor="middle" font-size="17" class="tm-text-accent" direction="rtl">نامرتب</text><rect x="265" y="418" width="80" height="70" rx="8" class="tm-green"/><rect x="360" y="418" width="80" height="70" rx="8" class="tm-gold tm-pulse"/><rect x="455" y="418" width="80" height="70" rx="8" class="tm-green"/><g text-anchor="middle" font-size="18"><text x="305" y="444" class="tm-text">4</text><text x="400" y="444" class="tm-text">2</text><text x="495" y="444" class="tm-text">4</text><text x="305" y="475" class="tm-text" direction="rtl">درست</text><text x="400" y="475" class="tm-text" direction="rtl">غلط</text><text x="495" y="475" class="tm-text" direction="rtl">درست</text></g><text x="400" y="513" text-anchor="middle" font-size="16" class="tm-text-accent" direction="rtl">بدون تضمین یکنواختی، این الگو قابل اتکا نیست</text></svg>
```
lower bound با بازهٔ نیمهباز
در آرایهٔ مرتب، lower bound اندیس اولین عضو با مقدار \(\ge target\) است؛ اگر چنین عضوی نباشد، پاسخ \(n\) است. \(n=\operatorname{len}(nums)\)
**شروع تابع lowerbound**
\[ lo=0,\qquad hi=n,\qquad [lo,hi) \]
ورودیها: nums و target؛ سر راست بازه داخل نیست.
**بدنهٔ حلقه**
\[ \begin{gathered}lo<hi\\mid=lo+\left\lfloor\frac{hi-lo}{2}\right\rfloor\\\begin{cases}lo\gets mid+1&nums[mid]<target\\hi\gets mid&nums[mid]\ge target\end{cases}\end{gathered} \]
**پس از حلقه**
\[ \operatorname{return}\;lo \]
**مثال: مقایسهٔ اول**
\[ \begin{gathered}nums=[2,4,4,4,7],\quad target=4\(lo,hi)=(0,5)\\mid=0+\lfloor(5-0)/2\rfloor=2\\nums[2]=4\ge4\quad\Longrightarrow\quad hi=2\end{gathered} \]
**مقایسهٔ دوم**
\[ \begin{gathered}(lo,hi)=(0,2)\\mid=0+\lfloor(2-0)/2\rfloor=1\\nums[1]=4\ge4\quad\Longrightarrow\quad hi=1\end{gathered} \]
**مقایسهٔ سوم و پاسخ**
\[ \begin{gathered}(lo,hi)=(0,1)\\mid=0+\lfloor(1-0)/2\rfloor=0\\nums[0]=2<4\quad\Longrightarrow\quad lo=1\\lo=hi=1\quad\Longrightarrow\quad\operatorname{return}\;1\end{gathered} \]
**loop invariant: دو ناحیهٔ قطعی**
\[ \begin{gathered}0\le lo\le hi\le n\\0\le i<lo\quad\Longrightarrow\quad nums[i]<target\\hi\le i<n\quad\Longrightarrow\quad nums[i]\ge target\end{gathered} \]
ابتدا هر دو ناحیه خالیاند؛ مرتب بودن، حذف یک تکهٔ کامل را ممکن میکند.
**بازهٔ خالی، مرز پیدا شده**
\[ lo=hi\quad\Longrightarrow\quad[lo,hi)=\varnothing \]
lo مرز بین مقادیر کوچکتر و مقادیر بزرگتر یا مساوی target است.
**دسترسی امن و پایان قطعی**
\[ \begin{gathered}lo<hi\quad\Longrightarrow\quad0\le lo\le mid<hi\le n\\d=hi-lo>0\quad\Longrightarrow\quad0\le d_{\mathrm{new}}<d\end{gathered} \]
mid داخل آرایه است؛ هر دور lo جلو میرود یا hi عقب میآید.
**ورودی خالی**
\[ n=0\quad\Longrightarrow\quad lo=hi=0\quad\Longrightarrow\quad\operatorname{return}\;0 \]
حلقه اجرا نمیشود.
عبور از مساوی برای آخرین رخداد
در برخورد با مقدار مساوی، بمانیم یا رد شویم؟
**آرایهٔ مرتب**
\[ \mathrm{nums}=[2,4,4,4,7],\qquad \mathrm{target}=4 \]
**تعریف upper bound**
\[ P(i)\equiv \mathrm{nums}[i]>\mathrm{target},\qquad P=[\mathrm{false},\mathrm{false},\mathrm{false},\mathrm{false},\mathrm{true}] \]
اولین اندیس با مقدار واقعاً بزرگتر از target
**تنها تغییر در مقایسه**
\[ \begin{aligned}\mathrm{mid}&=\mathrm{lo}+\left\lfloor\frac{\mathrm{hi}-\mathrm{lo}}{2}\right\rfloor\\\mathrm{nums}[\mathrm{mid}]\le\mathrm{target}&\Rightarrow \mathrm{lo}\leftarrow\mathrm{mid}+1\\\mathrm{nums}[\mathrm{mid}]>\mathrm{target}&\Rightarrow \mathrm{hi}\leftarrow\mathrm{mid}\end{aligned} \]
شروع، شرط حلقه و برگردوندن lo مثل lowerbound هستند.
**عبور از مقدار مساوی**
\[ \begin{aligned}[\mathrm{lo},\mathrm{hi})&=[0,5)\\\mathrm{mid}&=2,\quad \mathrm{nums}[2]=4\le4\\\mathrm{lo}&\leftarrow3\quad\Rightarrow\quad[3,5)\end{aligned} \]
**حذف مقدار بزرگتر**
\[ \begin{aligned}\mathrm{mid}&=4,\quad \mathrm{nums}[4]=7>4\\\mathrm{hi}&\leftarrow4\quad\Rightarrow\quad[3,4)\end{aligned} \]
**عبور از آخرین مقدار مساوی**
\[ \begin{aligned}\mathrm{mid}&=3,\quad \mathrm{nums}[3]=4\le4\\\mathrm{lo}&\leftarrow4\quad\Rightarrow\quad[4,4)\\\mathrm{lo}&=\mathrm{hi}=4\quad\Rightarrow\quad\mathrm{upperbound}=4\end{aligned} \]
**ناحیههای قطعی در invariant**
\[ \begin{aligned}0\le i<\mathrm{lo}&\Rightarrow\mathrm{nums}[i]\le\mathrm{target}\\\mathrm{hi}\le i<n&\Rightarrow\mathrm{nums}[i]>\mathrm{target}\end{aligned} \]
**از مرزها به آخرین رخداد**
\[ \begin{aligned}\mathrm{lowerbound}&=1,\qquad\mathrm{upperbound}=4\[\mathrm{lowerbound},\mathrm{upperbound})&=[1,4)\\\mathrm{last}&=\mathrm{upperbound}-1=4-1=3\end{aligned} \]
upper bound آخرین رخداد نیست؛ مرز بعد از رخدادهاست. مساویشدن در هیچکدام دلیل توقف نیست.
ترکیب مرزها و بررسی حضور
**تابع نهایی و تستهای مرزی**
```python
def searchrange(nums, target):
first = lowerbound(nums, target)
if first == len(nums) or nums[first] != target:
return [-1, -1]
stop = upperbound(nums, target)
return [first, stop - 1]
```
**ترتیب شرطها مهم است:** اگر `first == len(nums)` درست باشد، Python عبارت `nums[first] != target` را بررسی نمیکند؛ دسترسی خارج از آرایه رخ نمیدهد.
**چرا lower bound کافی نیست؟** در مثال قبلی، با \(target=5\):
\[
\begin{aligned}
mid=2,\ nums[2]=4 &\Rightarrow lo=3\\
mid=4,\ nums[4]=7 &\Rightarrow hi=4\\
mid=3,\ nums[3]=4 &\Rightarrow lo=4\\
first=4,\ nums[4]=7\ne5 &\Rightarrow [-1,-1]
\end{aligned}
\]
**Edge Caseها**
| ورودی و هدف | مسیر مرزها و اعتبارسنجی | پاسخ |
|---|---|---|
| \(nums=[]\)، هر هدف | \(first=0=\operatorname{len}(nums)\)؛ بدون خواندن عضو | \([-1,-1]\) |
| \(nums=[4,4,4],\ target=4\) | lower bound: \(mid:1\to0\Rightarrow first=0\)؛ upper bound: \((mid,lo):(1,2)\to(2,3)\Rightarrow stop=3\) | \([0,2]\) |
| \(nums=[4,4,4],\ target=5\) | \((mid,lo):(1,2)\to(2,3)\Rightarrow first=3=\operatorname{len}(nums)\) | \([-1,-1]\) |
| \(nums=[4,4,4],\ target=3\) | \(first=0\)، ولی \(nums[0]=4\ne3\) | \([-1,-1]\) |
| \(nums=[4],\ target=4\) | \(first=0,\ stop=1\Rightarrow[first,stop-1]=[0,0]\) | \([0,0]\) |
**دو انتهای مثال اصلی:** \(target=2\Rightarrow[0,0]\) و \(target=7\Rightarrow[4,4]\).
پیشرفت، هزینه و آزمون مستقل
بررسی خطاها در قالب نیمهباز \([lo,hi)\)
**خطای اول: توقف پیشرفت**
\[ \begin{aligned}a&=[2],\quad target=4\(lo,hi,mid)&=(0,1,0)\\a[0]<4,\quad lo\gets mid&=0\[0,1)&\longrightarrow[0,1)\longrightarrow\cdots\end{aligned} \]
حلقه تمام نمیشود؛ بهروزرسانی درست: \(lo\gets mid+1\).
**خطای دوم: شروع ناسازگار**
\[ \begin{aligned}a&=[2],\quad target=4\\hi\gets n-1&=0,\quad lo=0\\lo<hi&:\quad 0<0\quad\text{(false)}\\\text{return }lo&=0\ne1\end{aligned} \]
حلقه اجرا نمیشود؛ مرز درست \(1\) است.
**شرط ناسازگار روی ورودی خالی**
\[ \begin{aligned}a&=[],\quad lo=hi=0\\lo\le hi&:\quad 0\le0\quad\text{(true)}\\mid&=0,\quad a[0]\;\text{undefined}\end{aligned} \]
قرارداد سازگار: \(hi=n\)، شرط \(lo<hi\)، و بهروزرسانیهای \(lo=mid+1\) یا \(hi=mid\).
**نصفشدن بازه**
\[ 8\longrightarrow4\longrightarrow2\longrightarrow1\longrightarrow0 \]
حداکثر تعداد اعضای باقیمانده پس از هر دور؛ تعداد دورها لگاریتمی است.
**زمان دو جستوجو**
\[ \begin{aligned}T_{\mathrm{search}}(n)&=O(\log n)\quad(n\ge2)\\T_{\mathrm{total}}(n)&=2\,O(\log n)=O(\log n)\\T(0),\ T(1)&=O(1)\end{aligned} \]
با فرض دسترسی و مقایسهٔ ثابتزمان.
**حافظهٔ کمکی ثابت**
\[ S_{\mathrm{aux}}(n)=O(1) \]
فقط چند متغیر اندیس؛ بدون slicing، کپی یا مرتبسازی.
**تمرین: ابتدا مرزها را پیشبینی کن**
\[ a=[1,3,3,6],\qquad target=3 \]
هر دو تابع مرزی و تابع نهایی را از حافظه بنویس.
**از دو مرز تا پاسخ**
\[ \begin{aligned}\mathrm{lower\ bound}(3)&=1\\\mathrm{upper\ bound}(3)&=3\[\mathrm{first},\mathrm{last}]&=[1,3-1]=[1,2]\end{aligned} \]
چرا هر حذف امن است؟ چرا حلقه جلو میرود؟
**آزمون هدفهای غایب**
\[ \begin{aligned}target=0:&\quad L=U=0\quad\Rightarrow\quad 0\notin a\\target=8:&\quad L=U=4\quad\Rightarrow\quad 8\notin a\end{aligned} \]
قرارداد، انتخاب راهحل، کدنویسی و تست را روشن توضیح بده.
بازگشت به دوره