092 — Lower Bound

091-এ exact target খুঁজলে। কিন্তু আসল জীবনে আরও দরকারি প্রশ্ন প্রায়ই অন্যরকম: "x যদি না-ও থাকে, তবে সাজানো ক্রম রক্ষা করে সে কোথায় বসবে?" এই note সেই প্রশ্নের উত্তর — lower bound। এটাই Python-এর বিখ্যাত bisect_left-এর হৃদয়, আর এর উপরেই 094 (insert position) আর 101 (median) দাঁড়াবে। ধীরে পড়ো — duplicate কীভাবে সামলায়, সেটাই এখানে মজা।

Source

• Original source: Classic exercise (Python-এর bisect.bisect_left-এর হাতে-বানানো রূপ)
• Platform: — (standard library concept; related: Python docs — https://docs.python.org/3/library/bisect.html)
• 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

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) (একদম শেষের পরে)।

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 (সীমানা) খোঁজা।

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।

4. Real-life analogy

ভাবো লাইব্রেরিতে বই sorted করে রাখা আছে catalog number অনুযায়ী, আর তুমি একটা নতুন বই (number x) তাকে রাখতে চাও — কিন্তু ক্রম নষ্ট না করে।

তুমি খুঁজছ প্রথম সেই জায়গা যেখান থেকে বইগুলোর number x বা তার চেয়ে বড়। সেই জায়গাটার ঠিক আগে তোমার নতুন বই গলিয়ে দিলেই ক্রম অটুট। যদি একই number-এর কয়েকটা বই আগে থেকেই থাকে, তুমি তাদের সবার বাঁয়ে (প্রথমটার আগে) বসাও — এটাই "left" bound।

5. Visual explanation

a = [1, 3, 3, 3, 7], x = 3। প্রতিটা index-এ "a[i] >= 3?" শর্তের সিঁড়ি:

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 মিথ্যা বলবে।

6. Example input and output

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।

7. Brute force thinking

সবচেয়ে সরল — বাঁ থেকে এক এক করে দেখো, প্রথম যেখানে a[i] >= x পেলে সেই index ফেরত:

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, এই দামি তথ্য কাজে লাগায় না; এক এক করে সব দেখে।

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 দিয়ে খুঁজি:

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-এর প্রাণ।

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।

12. Python solution

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

lo, hi = 0, len(a)

খেয়াল করো hi = len(a), 091-এর মতো len(a) - 1 না! কারণ উত্তর হতে পারে len(a)-ও (x সবার চেয়ে বড় হলে)। তাই range-টা [0, len(a)] ধরি।

while lo < hi:

<, <= না — এই template-এ lo == hi হলেই উত্তর পাওয়া গেছে, থামো।

if a[mid] < x: lo = mid + 1

a[mid] এখনো x-এর ছোট মানে mid নিশ্চিত প্রথম T না (এখনো F অঞ্চলে)। তাই mid সহ বাঁ অর্ধেক বাদ।

else: hi = mid

a[mid] >= x মানে mid নিজেই হয়তো সেই প্রথম T। তাই তাকে রেখে দিই (hi = mid, mid - 1 না), শুধু ডান দিক বাদ।

return lo

loop শেষে lo == hi — সেই প্রথম index যেখানে শর্ত সত্যি, অর্থাৎ lower bound।

cross-check-এ bisect_left আর brute force দুটোর সাথেই প্রতিটা x-এ উত্তর মিলিয়ে দেখছি। সব মিললে সব test pass!।

14. Output walkthrough

চালালে যা ছাপবে:

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!।

15. Time complexity

O(log n) — প্রতি ধাপে search space অর্ধেক, ঠিক 091-এর মতো। n যত বড়ই হোক, log₂(n) ধাপেই প্রথম T পাওয়া যায়।

16. Space complexity

O(1) — শুধু lo, hi, mid; কোনো বাড়তি array না। (cross-check-এর big list test-এর জন্য, মূল function-এর অংশ না।)

17. Common mistakes

1. hi = mid - 1 লিখে ফেলা — তাহলে যে mid নিজেই প্রথম T, তাকে ফেলে দাও → উত্তর এক ঘর বেশি ডানে যায়। boundary search-এ hi = mid-ই নিয়ম।
2. hi = len(a) - 1 দিয়ে শুরু করা — তাহলে x সবার চেয়ে বড় হলে (return len(a) দরকার) উত্তর ভুল আসে। range [0, len(a)] রাখতে হয়।
3. while lo <= hi লেখা — hi = mid (mid - 1 না) থাকায় lo == hi অবস্থায় চিরকাল আটকে infinite loop। এই template-এ while lo < hi।
4. lower আর upper bound গুলিয়ে ফেলা — duplicate-এ দুটো আলাদা উত্তর দেয়: [3,3,3]-এ x=3 → lower 0, upper 3। শর্তে < বনাম <=-এর পার্থক্য (093 দেখো)।
5. "x আছে কিনা" আর "x কোথায় বসবে" মিলিয়ে ফেলা — lower bound আছে-নেই নির্বিশেষে একটা index দেয়; "আছে কিনা" জানতে আলাদা করে a[lb] == x (lb < len হলে) চেক করতে হয়।

18. Harder problems that inherit this idea

• LeetCode — Search Insert Position (https://leetcode.com/problems/search-insert-position/) — হুবহু lower bound; পরের problem 094-এই এর প্রয়োগ।
• LeetCode — Find First and Last Position (https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/) — lower bound দিয়ে first, upper bound দিয়ে last; দুটো একসাথে।
• 093 (Upper Bound) আর 101 (Median of Two Sorted Arrays) — এই repo-রই পরের ধাপ; 093 হলো এর যমজ ভাই, 101-এ partition-এর boundary খোঁজাও একই চিন্তা।

19. Pattern learned

Lower bound (first ≥ x) via boundary search — while lo < hi, a[mid] < x → lo = mid + 1, নইলে hi = mid। বড় শিক্ষা: exact match না খুঁজে, একটা monotonic শর্তের প্রথম T খোঁজাও binary search — আর "mid উত্তর হতে পারলে তাকে ফেলো না"। এটাই Python-এর bisect_left, আর গোটা BSoA-র boundary-খোঁজার কঙ্কাল।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "lower bound = প্রথম a[i] >= x; while lo < hi, F হলে lo = mid+1, নইলে hi = mid; hi = len(a) দিয়ে শুরু। = bisect_left। 'mid হয়তো প্রথম T' — তাই mid রেখে দাও। duplicate-এ বাঁ ঘেঁষে বসে।"

পরের ধাপ → 093 — Upper Bound (যমজ ভাই: প্রথম > x; শর্তে শুধু <=-এর ছোঁয়া)। সম্পর্কিত → 094 — Search Insert Position।

ফিরে দেখা: এই level-এর map → ../README.md · এই note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

21. JavaScript solution (with test cases)

boundary search — while lo < hi, আর hi = mid (mid - 1 নয়), কারণ mid নিজেই প্রথম T হতে পারে।

// 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) এখানে নিরাপদ।

22. TypeScript solution (with test cases)

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<readonly [number, number]> = [
  [3, 1], [4, 4], [1, 0], [8, 5], [0, 0],
];
for (const [x, want] of cases) expect(lowerBound(arr, x), want, `x=${x}`);
expect(lowerBound([], 5), 0, "empty");
console.log("সব TS test pass!");

TS টীকা: a: number[] ও return number declare করায় sorted-number ছাড়া input বাদ, আর "index/insert-position" মানে স্পষ্ট — caller যেন "found?" boolean ভেবে না নেয়, type সেটা মনে করায়।

23. কোথায় কাজে লাগে (real-world use)

• Sorted insert position: নতুন element কোথায় বসালে ক্রম অটুট — sorted list/leaderboard maintenance (bisect_left)।
• Range count via bounds: upperBound - lowerBound দিয়ে "x কতবার আছে" বা "[lo, hi] range-এ কয়টা" O(log n)-এ।
• Time-series / log search: নির্দিষ্ট timestamp থেকে শুরু হওয়া প্রথম event খোঁজা।
• Autocomplete prefix range: sorted শব্দে একটা prefix-এর প্রথম ও পরের boundary বের করা। মূল pattern — "exact নয়, একটা monotonic শর্তের প্রথম T খোঁজা; mid উত্তর হতে পারলে ফেলো না" — boundary search, answer-space binary search জুড়ে বড় ছবিতে ফেরে।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখো; problem statement copy কোরো না; official link শুধু attribution-এর জন্য রাখো; "asked by Google/Amazon" এমন দাবি কোরো না — বরং "Google-style pattern" / "common interview pattern" লেখো।