091 — Basic Binary Search

এই note দিয়ে Level 7 শুরু — অভিনন্দন! ছোটবেলার "1 থেকে 100-এর মধ্যে একটা সংখ্যা ভেবেছি" খেলাটা মনে আছে? প্রতিটা guess-এ অর্ধেক জগৎ মুছে যেত। সেই খেলাটাই এবার sorted array-তে নামাব। ধীরে পড়ো, তাড়া নেই — এই একটা problem-এর lo/hi invariant পাকা হলে গোটা level সহজ হয়ে যাবে। "vule gesi" হলেও সমস্যা নেই, এই note ধরে ধরে আবার গেঁথে যাবে।

Source

• Original source: LeetCode Binary Search
• Platform: LeetCode — https://leetcode.com/problems/binary-search/
• Topic: Math-based programming fundamentals → Level 7: Binary Search on Answer
• Difficulty: Easy
• Pattern: halving (search space অর্ধেক করা)
• Basic idea inherited from: — (এটাই এই level-এর শিকড়, আগে কিছু নেই)

1. Problem in simple words

একটা sorted (ছোট থেকে বড় সাজানো) array a দেওয়া আছে আর একটা target সংখ্যা x। বলতে হবে — x কি array-তে আছে? থাকলে তার index ফেরত দাও; না থাকলে -1।

শর্ত একটাই, কিন্তু সেটাই সব: array টা আগে থেকে sorted। এই sorted হওয়াটাই আমাদের অর্ধেক-অর্ধেক বাদ দেওয়ার অধিকার দেয়।

দেখতে সাধারণ, কিন্তু interview-তে এই একটা জিনিস bug-free লিখতে পারাটাই আসল ভিত — কারণ এর উপরেই পরের সব binary search দাঁড়াবে।

2. What is the math idea?

মূল idea — প্রতি ধাপে অর্ধেক সম্ভাবনা মুছে ফেলা। array sorted বলে মাঝখানের element a[mid] দেখলেই বুঝে যাই target কোন পাশে:

• a[mid] == x → পেয়ে গেছি
• a[mid] < x → target আরও বড়, তাই বাঁ অর্ধেক (mid সহ) পুরোটা বাদ
• a[mid] > x → target আরও ছোট, তাই ডান অর্ধেক (mid সহ) পুরোটা বাদ

n টা element থেকে 1-এ নামতে লাগে মাত্র log₂(n) ধাপ। এটাই binary search-কে এত দ্রুত বানায়।

3. Which basic idea does this inherit from?

এটা এই level-এর প্রথম problem, তাই উপরে দাঁড়ানোর মতো আগের কোনো binary search নেই (তাই "inherited from: —")।

বরং উল্টোটা — এটাই সেই বীজ। এখানকার lo/hi/mid invariant আর "অর্ধেক বাদ" চিন্তা সরাসরি কাজে লাগবে:

• 092 (Lower Bound) — একই কাঠামো, শুধু "প্রথম ≥ x" খোঁজে
• 095 (Square Root) — array উধাও, তবু একই অর্ধেক-অর্ধেক খেলা উত্তরের উপর

মানে আজ তুমি শুধু একটা search শিখছ না — তুমি গোটা level-এর template-এর সাথে প্রথম পরিচয় করছ।

4. Real-life analogy

ভাবো তোমার হাতে একটা মোটা dictionary, খুঁজছ "monsoon" শব্দটা। তুমি কি প্রথম পাতা থেকে এক এক করে পড়া শুরু করবে? না!

তুমি বইটা মাঝখানে খোলো — হয়তো "M" পেরিয়ে "P"-তে পড়লে। তখন পেছনের অর্ধেক পুরোটা বন্ধ করে দাও, শুধু সামনের অর্ধেকে খোঁজো। আবার সেই অর্ধেকের মাঝে খোলো। প্রতিবার অর্ধেক বই বাদ — কয়েকবারেই "monsoon"-এ পৌঁছে যাও।

dictionary sorted (alphabetical) বলেই এটা সম্ভব। এলোমেলো বইয়ে এই কৌশল খাটে না — ঠিক যেমন unsorted array-তে binary search চলে না।

5. Visual explanation

a = [2, 5, 8, 12, 16, 23], x = 16 খুঁজছি। প্রতিটা ধাপে অর্ধেক কীভাবে মুছে যায় দেখো:

step 1:  [ 2   5   8  12  16  23 ]      lo=0, hi=5, mid=2
          ↑       ↑           ↑
          lo     mid          hi        a[2]=8 < 16  →  বাঁ অর্ধেক বাদ

step 2:  [ x   x   x  12  16  23 ]      lo=3, hi=5, mid=4
                      ↑   ↑   ↑
                      lo mid  hi        a[4]=16 == 16  →  পাওয়া গেল! index 4

x = বাদ পড়া ঘর।  প্রতি ধাপে অর্ধেক জগৎ মুছে যাচ্ছে।

invariant-টা মুখে বলো: "x যদি থাকে, তবে [lo, hi]-এর ভেতরেই আছে।" প্রতিটা update এই বাক্যটা সত্য রাখে।

6. Example input and output

a (sorted)                  x    ->  output
--------------------------------------------
[2, 5, 8, 12, 16, 23]      16   ->  4      (index 4-এ আছে)
[2, 5, 8, 12, 16, 23]       2   ->  0      (একদম প্রথমে)
[2, 5, 8, 12, 16, 23]      23   ->  5      (একদম শেষে)
[2, 5, 8, 12, 16, 23]      10   ->  -1     (নেই)
[]                          5   ->  -1     (খালি array)
[7]                         7   ->  0      (এক element)

খেয়াল করো edge case গুলো: খালি array (-1), এক element, আর target যদি প্রথম/শেষে থাকে — এখানেই বেশির ভাগ bug লুকায়।

7. Brute force thinking

প্রথমে মাথায় আসে সবচেয়ে সরল জিনিস — এক এক করে সব দেখা (linear search):

def search_brute(a, x):
    for i in range(len(a)):
        if a[i] == x:
            return i
    return -1

array-টা sorted কিনা এটা পাত্তাই দেয় না — শুরু থেকে শেষ পর্যন্ত প্রতিটা element তুলনা করে। ঠিক উত্তরই দেয়, লিখতেও সহজ।

8. Why brute force may be slow

সমস্যা হলো এটা সবচেয়ে খারাপ ক্ষেত্রে (target শেষে বা নেই) পুরো array ঘোরে — O(n)। array-টা যে sorted, সেই দামি তথ্যটা একদম কাজে লাগায় না।

n = 1,000,000 হলে:
  linear search : ~1,000,000 বার তুলনা  (ধীর, O(n))
  binary search : ~20 বার তুলনা          (log₂(1000000) ≈ 20, O(log n))

মূল শিক্ষা: array sorted থাকলে এক এক করে দেখা অপচয় — মাঝখান দেখেই অর্ধেক বাদ দেওয়া যায়।

9. Better thinking

মূল insight: sorted array-তে মাঝখানের element দেখলেই target কোন পাশে, তা নিশ্চিতভাবে জানা যায়। তাই প্রতি ধাপে অর্ধেক ফেলে দাও।

def binary_search(a, x):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == x:
            return mid
        if a[mid] < x:
            lo = mid + 1        # বাঁ অর্ধেক বাদ
        else:
            hi = mid - 1        # ডান অর্ধেক বাদ
    return -1

প্রতি ধাপে search space অর্ধেক → মোট log₂(n) ধাপ → O(log n)।

10. Thinking tweak

আসল "আহা!" মুহূর্ত: পুরো array না দেখে, প্রতি প্রশ্নে শুধু একটা element (মাঝখানেরটা) দেখেই অর্ধেক উত্তর-জগৎ ফেলে দেওয়া যায় — যদি array sorted হয়।

এই decomposition-টা মাথায় গেঁথে নাও — "একটা প্রশ্ন, যার উত্তরে অর্ধেক মুছে যায়"। পরের সব problem-এ array-র জায়গায় বসবে answer space, আর a[mid] == x তুলনার জায়গায় বসবে একটা feasibility check। কিন্তু কঙ্কালটা ঠিক এটাই।

11. Step-by-step dry run

a = [2, 5, 8, 12, 16, 23], x = 16 ধীরে চালাই:

step	lo	hi	mid	a[mid]	তুলনা	সিদ্ধান্ত
1	0	5	2	8	8 < 16	lo = mid + 1 = 3
2	3	5	4	16	16 == 16	return 4

দুই ধাপেই পাওয়া গেল। এবার একটা "নেই"-এর কেস, x = 10:

step	lo	hi	mid	a[mid]	তুলনা	সিদ্ধান্ত
1	0	5	2	8	8 < 10	lo = 3
2	3	5	4	16	16 > 10	hi = 3
3	3	3	3	12	12 > 10	hi = 2
—	3	2	—	—	lo > hi	loop থামল → return -1

lo > hi হওয়া মানে range খালি — target নেই।

12. Python solution

def binary_search(a, x):
    """sorted array a-তে x-এর index দেয়, না থাকলে -1।"""
    lo, hi = 0, len(a) - 1
    while lo <= hi:                  # [lo, hi] range খালি না হওয়া পর্যন্ত
        mid = (lo + hi) // 2
        if a[mid] == x:
            return mid               # পেয়ে গেছি
        if a[mid] < x:
            lo = mid + 1             # বাঁ অর্ধেক (mid সহ) বাদ
        else:
            hi = mid - 1             # ডান অর্ধেক (mid সহ) বাদ
    return -1                        # range ফুরিয়ে গেল, নেই


# --- ছোট test গুলো (সব pass করা উচিত) ---
a = [2, 5, 8, 12, 16, 23]
assert binary_search(a, 16) == 4
assert binary_search(a, 2) == 0          # প্রথম element
assert binary_search(a, 23) == 5         # শেষ element
assert binary_search(a, 10) == -1        # নেই
assert binary_search([], 5) == -1        # খালি array
assert binary_search([7], 7) == 0        # এক element, আছে
assert binary_search([7], 9) == -1       # এক element, নেই

# brute force-এর সাথে মিলিয়ে দেখি (cross-check)
def search_brute(arr, t):
    for i in range(len(arr)):
        if arr[i] == t:
            return i
    return -1

big = list(range(0, 200, 2))             # [0, 2, 4, ..., 198]
for t in range(-1, 200):
    assert binary_search(big, t) == search_brute(big, t)

print(binary_search(a, 16))   # 4
print(binary_search(a, 10))   # -1
print("সব test pass!")

13. Line-by-line explanation

lo, hi = 0, len(a) - 1

lo আর hi হলো search range-এর দুই সীমা — শুরুতে পুরো array (প্রথম থেকে শেষ index)।

while lo <= hi:

যতক্ষণ range-এ অন্তত একটা element আছে (lo <= hi), খোঁজা চালিয়ে যাও। lo > hi হলে range খালি — থামো।

mid = (lo + hi) // 2

মাঝখানের index। // 2 integer division, তাই মাঝে দুটো element থাকলে বাঁ দিকেরটা নেয়।

if a[mid] == x: return mid

মাঝখানেই target পেলে সরাসরি index ফেরত — কাজ শেষ।

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

মাঝখানের মান target-এর ছোট মানে target ডান পাশে। তাই mid সহ বাঁ অর্ধেক বাদ — নতুন lo হয় mid + 1।

else: hi = mid - 1

উল্টোটা — মাঝখানের মান বড়, target বাঁ পাশে। mid সহ ডান অর্ধেক বাদ।

বাকি assert গুলো নিজেদের যাচাই করছে; cross-check-এ brute force-এর সাথে প্রতিটা উত্তর মিলিয়ে দেখছি। সব ঠিক থাকলে শেষে সব test pass! ছাপে।

14. Output walkthrough

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

4
-1
সব test pass!

প্রথম লাইন binary_search(a, 16) থেকে — index 4। দ্বিতীয় লাইন binary_search(a, 10) থেকে — 10 নেই, তাই -1। তার আগের সব assert (cross-check সহ) চুপচাপ pass করেছে। সবশেষে সব test pass! — সব ঠিক আছে।

15. Time complexity

O(log n) — প্রতি ধাপে search space ঠিক অর্ধেক হয়, তাই n থেকে 1-এ নামতে log₂(n) ধাপ। 10 লক্ষ element-এও মাত্র ~20 ধাপ।

16. Space complexity

O(1) — কোনো বাড়তি array বা list লাগছে না; শুধু lo, hi, mid — গুটিকয় variable। (এটা iterative version; recursive লিখলে call stack-এ O(log n) লাগত।)

17. Common mistakes

1. Unsorted array-তে চালানো — binary search-এর পুরো ভিত্তি sorted হওয়া; এলোমেলো array-তে এটা ভুল উত্তর দেয়।
2. while lo < hi বনাম while lo <= hi গুলিয়ে ফেলা — exact search-এ <= লাগে (নইলে শেষ একটা element মিস হয়); lower/upper bound-এ < লাগে। দুটো আলাদা template।
3. lo = mid বা hi = mid লেখা — exact search-এ mid ইতিমধ্যে দেখা হয়ে গেছে, তাই mid + 1 / mid - 1; নইলে lo/hi আটকে গিয়ে infinite loop।
4. খালি array ভুলে যাওয়া — len(a) - 1 হয় -1, তখন lo <= hi মানে 0 <= -1 → false → সরাসরি -1, কাজ করে। কিন্তু হাতে যাচাই করা উচিত।
5. Overflow (অন্য ভাষায়) — C++/Java-তে (lo + hi) বড় সংখ্যায় overflow করতে পারে; নিরাপদ লেখা lo + (hi - lo) // 2। Python-এ এ সমস্যা নেই (বড় int নিজেই সামলায়)।

18. Harder problems that inherit this idea

• LeetCode — Search in Rotated Sorted Array (https://leetcode.com/problems/search-in-rotated-sorted-array/) — একই অর্ধেক-বাদ চিন্তা, কিন্তু কোন অর্ধেক sorted সেটা আগে বুঝতে হয়।
• LeetCode — Find First and Last Position (https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/) — দুটো binary search: lower আর upper bound (092, 093-এর সরাসরি প্রয়োগ)।
• 092 (Lower Bound) আর 095 (Square Root) — এই repo-রই পরের ধাপ, যেখানে এই template বাঁক নেয় আর array ছাড়াই চলতে শেখে।

19. Pattern learned

Halving via sorted order — sorted array-তে মাঝখান দেখে প্রতি ধাপে অর্ধেক বাদ; while lo <= hi + mid ± 1। বড় শিক্ষা: একটা ভালো প্রশ্ন (এর চেয়ে বড়/ছোট?) প্রতিবার অর্ধেক সম্ভাবনা মুছে দেয় — খোঁজার কাজ O(n) থেকে O(log n)-এ নামে। এই "অর্ধেক বাদ" চোখটাই গোটা level-এর ভিত্তি।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "sorted array + target → while lo <= hi, mid = (lo+hi)//2; a[mid] দেখে অর্ধেক বাদ। invariant: x থাকলে [lo, hi]-তেই আছে। এটাই Level 7-এর কঙ্কাল — পরে array-র জায়গায় answer space, তুলনার জায়গায় check বসবে।"

পরের ধাপ → 092 — Lower Bound (একই template, কিন্তু "প্রথম ≥ x" খুঁজবে — duplicate থাকলেও)। সম্পর্কিত → 095 — Square Root using Binary Search।

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

21. JavaScript solution (with test cases)

JS-এ (lo + hi) / 2 float দেয়, তাই Math.floor দিয়ে integer mid নিই — exact search-এ lo <= hi আর mid ± 1।

// throwing assert — fail করলে থেমে error দেবে
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };

function binarySearch(a, x) {
  let lo = 0, hi = a.length - 1;
  while (lo <= hi) {                       // [lo, hi] খালি না হওয়া পর্যন্ত
    const mid = Math.floor((lo + hi) / 2); // integer division নেই → Math.floor
    if (a[mid] === x) return mid;
    if (a[mid] < x) lo = mid + 1;          // বাঁ অর্ধেক বাদ
    else hi = mid - 1;                      // ডান অর্ধেক বাদ
  }
  return -1;
}

// linear — cross-check
const searchBrute = (a, x) => { for (let i = 0; i < a.length; i++) if (a[i] === x) return i; return -1; };

// ---- test cases (file-এর example + edge case) ----
const a = [2, 5, 8, 12, 16, 23];
assert(binarySearch(a, 16) === 4, "16");
assert(binarySearch(a, 2) === 0, "প্রথম");
assert(binarySearch(a, 23) === 5, "শেষ");
assert(binarySearch(a, 10) === -1, "নেই");
assert(binarySearch([], 5) === -1, "খালি");
assert(binarySearch([7], 7) === 0, "এক element আছে");
assert(binarySearch([7], 9) === -1, "এক element নেই");
// brute-এর সাথে মিল: [0,2,4,...,198], target -1..199
const big = [];
for (let v = 0; v < 200; v += 2) big.push(v);
for (let t = -1; t < 200; t++) assert(binarySearch(big, t) === searchBrute(big, t), "cross " + t);
console.log("সব JS test pass!");

JS টীকা: integer division নেই, তাই mid = Math.floor((lo + hi) / 2); (lo + hi) >> 1-ও চলে কিন্তু বড় index-এ 32-bit সীমা আছে। Python-এ overflow নেই, JS number-ও বড়, তবু safe লেখা lo + Math.floor((hi - lo) / 2)।

22. TypeScript solution (with test cases)

function binarySearch(a: number[], x: number): number {
  let lo = 0, hi = a.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (a[mid] === x) return mid;
    if (a[mid] < x) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

function expect(actual: number, expected: number, msg = ""): void {
  if (actual !== expected) throw new Error(`FAIL ${msg}: ${actual}`);
}

const arr: number[] = [2, 5, 8, 12, 16, 23];
const cases: ReadonlyArray<readonly [number, number]> = [
  [16, 4], [2, 0], [23, 5], [10, -1],
];
for (const [x, want] of cases) expect(binarySearch(arr, x), want, `x=${x}`);
expect(binarySearch([], 5), -1, "empty");
expect(binarySearch([7], 7), 0, "single");
console.log("সব TS test pass!");

TS টীকা: a: number[] declare করায় sorted-number ছাড়া অন্য কিছু (string[], mixed) compile-time-এ বাদ; return number (index বা -1) স্পষ্ট, তাই caller ভুলে boolean-এর মতো ব্যবহার করলে ধরা পড়ে।

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

• Sorted data lookup: sorted array/DB index/Array.prototype-এ দ্রুত খোঁজা — O(log n), linear scan-এর বদলে।
• Autocomplete / dictionary: sorted শব্দতালিকায় prefix বা exact match দ্রুত বের করা।
• Version / commit bisect: git bisect-এর মতো — কোন version-এ bug ঢুকল তা log n ধাপে।
• Library bisect/lowerBound: insert position, range query, sorted set maintenance-এর ভিত্তি। মূল pattern — "একটা ভালো প্রশ্নে প্রতিবার অর্ধেক সম্ভাবনা মুছে ফেলা (O(n) → O(log n))" — binary search on answer, divide-and-conquer জুড়ে বড় ছবিতে ফেরে।

---

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