Problem link ও উৎস
- **Original source:** Classic exercise (Python-এর `bisect.bisect_left`-এর হাতে-বানানো রূপ)
- **Platform:** — (standard library concept; related: Python docs —
)
- **Topic:** Math-based programming fundamentals → Level 7: Binary Search on Answer
- **Difficulty:** Easy
- **Pattern:** first ≥ x (প্রথম যেখানে `a[i] >= x`)
- **Basic idea inherited from:** 091 — Basic Binary Search
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা **sorted** array `a` আর একটা সংখ্যা `x` দেওয়া। বলতে হবে — **সবচেয়ে ছোট index `i`** যেখানে `a[i] >= x`। অর্থাৎ প্রথম জায়গা যেখানে x বা তার চেয়ে বড় কেউ আছে।
আরেকভাবে দেখো: x-কে যদি array-তে ঢোকাতে হয় (sorted রাখতে রাখতে), তবে **বাঁ দিক ঘেঁষে** সে কোন index-এ বসবে — সেটাই lower bound।
বিশেষ কথা: x array-তে থাকতেও পারে, না-ও পারে। থাকলে lower bound তার **প্রথম occurrence**-এ আঙুল রাখে; না থাকলে যেখানে বসত সেখানে। আর x সবার চেয়ে বড় হলে উত্তর `len(a)` (একদম শেষের পরে)।
### Input ও output {#6-example-input-and-output}
```text
a (sorted) x -> lower bound (ব্যাখ্যা)
-----------------------------------------------------
[1, 3, 3, 3, 7] 3 -> 1 (প্রথম 3-এর index)
[1, 3, 3, 3, 7] 4 -> 4 (4 নেই; 7-এর আগে বসত)
[1, 3, 3, 3, 7] 1 -> 0 (একদম শুরুতে)
[1, 3, 3, 3, 7] 8 -> 5 (সবার চেয়ে বড়; শেষের পরে = len)
[1, 3, 3, 3, 7] 0 -> 0 (সবার চেয়ে ছোট; শুরুতে)
[] 5 -> 0 (খালি array)
```
দুটো edge খেয়াল করো: x সবার চেয়ে **বড়** হলে উত্তর `len(a)` (array-র বাইরে, কিন্তু বৈধ insert position), আর **খালি array**-তে উত্তর 0।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো লাইব্রেরিতে বই sorted করে রাখা আছে catalog number অনুযায়ী, আর তুমি একটা নতুন বই (number `x`) তাকে রাখতে চাও — কিন্তু ক্রম নষ্ট না করে।
তুমি খুঁজছ প্রথম সেই জায়গা যেখান থেকে বইগুলোর number x বা তার চেয়ে বড়। সেই জায়গাটার ঠিক আগে তোমার নতুন বই গলিয়ে দিলেই ক্রম অটুট। যদি একই number-এর কয়েকটা বই আগে থেকেই থাকে, তুমি তাদের **সবার বাঁয়ে** (প্রথমটার আগে) বসাও — এটাই "left" bound।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
091 (Basic Binary Search)-এর `lo`/`hi`/`mid` কাঠামো সরাসরি এখানে আসে — কিন্তু দুটো গুরুত্বপূর্ণ বদল:
- 091-এ `while lo <= hi` আর `mid ± 1`; এখানে **`while lo < hi`** আর `hi = mid` (mid - 1 না!)।
- 091 exact match-এ থামত; এখানে কখনো থামি না — শেষে `lo` আর `hi` এক বিন্দুতে মিলে, সেটাই উত্তর।
কারণ এখানে `mid` নিজেই উত্তর হতে **পারে** — তাই তাকে ফেলে দেওয়া যায় না। এই subtle পার্থক্যটাই 091 থেকে 092-কে আলাদা করে, আর এটাই গোটা level-এর "boundary search" template।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea — **monotonic শর্তে binary search**। "`a[i] >= x`" শর্তটা একবার সত্যি হলে, ডান দিকে সব index-এও সত্যি থাকে (array sorted বলে)। তাই শর্তের উত্তরগুলো সাজালে একটা সিঁড়ি: **F F F T T T** — প্রথম T-টাই আমাদের উত্তর।
এই "প্রথম T খোঁজা" হলো binary search-এর এক বিশেষ রূপ — exact match না, **boundary** (সীমানা) খোঁজা।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সবচেয়ে সরল — বাঁ থেকে এক এক করে দেখো, প্রথম যেখানে `a[i] >= x` পেলে সেই index ফেরত:
```python
def lower_bound_brute(a, x):
for i in range(len(a)):
if a[i] >= x:
return i
return len(a) # কেউ ≥ x না — শেষের পরে বসবে
```
`return len(a)` লাইনটা জরুরি: যদি কোনো element-ই x-এর সমান-বড় না হয় (x সবার চেয়ে বড়), তবে x বসবে একদম শেষে। ঠিক উত্তরই দেয়।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
এটা সবচেয়ে খারাপ ক্ষেত্রে পুরো array ঘোরে — **O(n)**। array sorted, এই দামি তথ্য কাজে লাগায় না; এক এক করে সব দেখে।
```text
n = 1,000,000 হলে:
linear scan : ~1,000,000 বার তুলনা (O(n))
binary search : ~20 বার তুলনা (O(log n))
```
প্রতিটা query যদি বারবার চালাতে হয় (যেমন কোনো বড় program-এ), এই পার্থক্যটা আকাশ-পাতাল।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight: শর্ত `a[i] >= x`-এর সিঁড়ি **F F F T T T** — monotonic। তাই **প্রথম T**-কে binary search দিয়ে খুঁজি:
```python
def lower_bound(a, x):
lo, hi = 0, len(a) # hi = len(a): "কেউ ≥ x না"-এর উত্তর
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < x:
lo = mid + 1 # mid নিশ্চিত উত্তর না (এখনো F অঞ্চলে)
else:
hi = mid # mid উত্তর হতে পারে — ফেলো না!
return lo
```
প্রতি ধাপে অর্ধেক → O(log n)।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল মোচড়: **mid যখন নিজেই উত্তর হতে পারে, তখন তাকে বাদ দিও না — `hi = mid` (mid - 1 নয়)।**
091-এ আমরা exact match পেলে থামতাম, তাই `mid` দেখা শেষ হলে নিরাপদে `mid ± 1`। কিন্তু এখানে আমরা প্রথম T খুঁজছি — `a[mid] >= x` হলে mid নিজেই হয়তো সেই প্রথম T! তাই তাকে রেখে দিই, শুধু ডান অর্ধেক ফেলি। আর `hi` যেহেতু `mid`-এ আসে, তাই `mid` নিচে ঝোঁকানো (`(lo + hi) // 2`) নিরাপদ — infinite loop হয় না। এই এক-শব্দের বদল (`mid` বনাম `mid - 1`) boundary search-এর প্রাণ।
### ছবিতে বোঝা {#5-visual-explanation}
`a = [1, 3, 3, 3, 7], x = 3`। প্রতিটা index-এ "`a[i] >= 3`?" শর্তের সিঁড়ি:
```text
a = [ 1 3 3 3 7 ]
index = 0 1 2 3 4 5 (শেষের পরে)
a[i]>=3 = F T T T T
↑
প্রথম T → lower bound = 1
তুলনায় upper bound (প্রথম > 3) = 4
ফারাক = 4 - 1 = 3 → মানে 3 আছে ঠিক 3 বার!
```
লক্ষ করো: সিঁড়িটা একবার T হলে আর F-এ ফেরে না — এই **monotonicity** ছাড়া binary search মিথ্যা বলবে।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`a = [1, 3, 3, 3, 7], x = 3` চালাই (`hi` শুরুতে `len(a) = 5`):
| step | lo | hi | mid | a[mid] | a[mid] < 3? | সিদ্ধান্ত |
| --- | --- | --- | --- | --- | --- | --- |
| 1 | 0 | 5 | 2 | 3 | না | hi = mid = 2 |
| 2 | 0 | 2 | 1 | 3 | না | hi = mid = 1 |
| 3 | 0 | 1 | 0 | 1 | হ্যাঁ | lo = mid + 1 = 1 |
| — | 1 | 1 | — | — | — | lo == hi → return 1 |
উত্তর 1 — প্রথম 3-এর index। লক্ষ করো শেষে `lo` আর `hi` মিলে 1-এ — সেটাই প্রথম T।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def lower_bound(a, x):
"""sorted a-তে প্রথম index যেখানে a[i] >= x; কেউ না থাকলে len(a)।"""
lo, hi = 0, len(a) # hi = len(a) যাতে "কেউ নেই" উত্তর দিতে পারে
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < x:
lo = mid + 1 # mid এখনো F — বাঁ অর্ধেক বাদ
else:
hi = mid # mid হয়তো প্রথম T — রেখে দাও
return lo # lo == hi: প্রথম T-এর জায়গা
# bisect_left দিয়ে cross-check করব
from bisect import bisect_left
def lower_bound_brute(a, x):
for i in range(len(a)):
if a[i] >= x:
return i
return len(a)
# --- ছোট test গুলো (সব pass করা উচিত) ---
a = [1, 3, 3, 3, 7]
assert lower_bound(a, 3) == 1 # প্রথম 3
assert lower_bound(a, 4) == 4 # 4 নেই, 7-এর আগে
assert lower_bound(a, 1) == 0 # সবচেয়ে ছোট
assert lower_bound(a, 8) == 5 # সবার চেয়ে বড় → len
assert lower_bound(a, 0) == 0 # সবার চেয়ে ছোট
assert lower_bound([], 5) == 0 # খালি array
# bisect_left আর brute force — দুটোর সাথেই মিলিয়ে দেখি
big = [0, 2, 2, 4, 4, 4, 6, 9, 9, 10]
for x in range(-2, 13):
assert lower_bound(big, x) == bisect_left(big, x)
assert lower_bound(big, x) == lower_bound_brute(big, x)
print(lower_bound(a, 3)) # 1
print(lower_bound(a, 4)) # 4
print(lower_bound(a, 8)) # 5
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
lo, hi = 0, len(a)
```
খেয়াল করো `hi = len(a)`, 091-এর মতো `len(a) - 1` না! কারণ উত্তর হতে পারে `len(a)`-ও (x সবার চেয়ে বড় হলে)। তাই range-টা `[0, len(a)]` ধরি।
```text
while lo < hi:
```
`<`, `<=` না — এই template-এ `lo == hi` হলেই উত্তর পাওয়া গেছে, থামো।
```text
if a[mid] < x: lo = mid + 1
```
`a[mid]` এখনো x-এর ছোট মানে mid নিশ্চিত প্রথম T না (এখনো F অঞ্চলে)। তাই mid সহ বাঁ অর্ধেক বাদ।
```text
else: hi = mid
```
`a[mid] >= x` মানে mid নিজেই হয়তো সেই প্রথম T। তাই তাকে রেখে দিই (`hi = mid`, mid - 1 না), শুধু ডান দিক বাদ।
```text
return lo
```
loop শেষে `lo == hi` — সেই প্রথম index যেখানে শর্ত সত্যি, অর্থাৎ lower bound।
cross-check-এ `bisect_left` আর brute force দুটোর সাথেই প্রতিটা x-এ উত্তর মিলিয়ে দেখছি। সব মিললে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
1
4
5
সব test pass!
```
প্রথম লাইন: `lower_bound(a, 3)` = 1 (প্রথম 3)। দ্বিতীয়: `lower_bound(a, 4)` = 4 (4 নেই, 7-এর আগে বসত)। তৃতীয়: `lower_bound(a, 8)` = 5 (8 সবার চেয়ে বড়, শেষের পরে = len)। আগের সব `assert` (bisect_left + brute force cross-check সহ) চুপচাপ pass। সবশেষে `সব test pass!`।
### JavaScript ও test cases {#21-javascript-solution-with-test-cases}
boundary search — `while lo < hi`, আর `hi = mid` (mid - 1 নয়), কারণ mid নিজেই প্রথম T হতে পারে।
```javascript
// throwing assert — fail করলে থেমে error দেবে
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
function lowerBound(a, x) {
let lo = 0, hi = a.length; // hi = len: "কেউ ≥ x না"-এর উত্তর
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (a[mid] < x) lo = mid + 1; // mid এখনো F → বাঁ অর্ধেক বাদ
else hi = mid; // mid হয়তো প্রথম T → রেখে দাও
}
return lo; // lo == hi: প্রথম T
}
// linear — cross-check
function lowerBoundBrute(a, x) {
for (let i = 0; i < a.length; i++) if (a[i] >= x) return i;
return a.length;
}
// ---- test cases (file-এর example + edge case) ----
const a = [1, 3, 3, 3, 7];
assert(lowerBound(a, 3) === 1, "প্রথম 3");
assert(lowerBound(a, 4) === 4, "4 নেই");
assert(lowerBound(a, 1) === 0, "সবচেয়ে ছোট");
assert(lowerBound(a, 8) === 5, "সবার চেয়ে বড় → len");
assert(lowerBound(a, 0) === 0, "0");
assert(lowerBound([], 5) === 0, "খালি array");
// brute-এর সাথে duplicate-ভরা array জুড়ে মিল
const big = [0, 2, 2, 4, 4, 4, 6, 9, 9, 10];
for (let x = -2; x < 13; x++) assert(lowerBound(big, x) === lowerBoundBrute(big, x), "cross " + x);
console.log("সব JS test pass!");
```
> **JS টীকা:** এই template-এ `hi = a.length` (091-এর `length - 1` নয়), কারণ উত্তর `len`-ও হতে পারে। `hi = mid` থাকায় অবশ্যই `while (lo < hi)` — `lo <= hi` দিলে `lo === hi`-তে চিরকাল আটকে infinite loop। mid নিচে-ঝোঁকা (`Math.floor`) এখানে নিরাপদ।
### TypeScript ও test cases {#22-typescript-solution-with-test-cases}
```typescript
function lowerBound(a: number[], x: number): number {
let lo = 0, hi = a.length;
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (a[mid] < x) lo = mid + 1;
else hi = mid;
}
return lo;
}
function expect(actual: number, expected: number, msg = ""): void {
if (actual !== expected) throw new Error(`FAIL ${msg}: ${actual}`);
}
const arr: number[] = [1, 3, 3, 3, 7];
const cases: ReadonlyArray