Problem link ও উৎস
- **Original source:** LeetCode Binary Search
- **Platform:** LeetCode —
- **Topic:** Math-based programming fundamentals → Level 7: Binary Search on Answer
- **Difficulty:** Easy
- **Pattern:** halving (search space অর্ধেক করা)
- **Basic idea inherited from:** — (এটাই এই level-এর শিকড়, আগে কিছু নেই)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা **sorted** (ছোট থেকে বড় সাজানো) array `a` দেওয়া আছে আর একটা target সংখ্যা `x`। বলতে হবে — `x` কি array-তে আছে? থাকলে তার **index** ফেরত দাও; না থাকলে `-1`।
শর্ত একটাই, কিন্তু সেটাই সব: array টা **আগে থেকে sorted**। এই sorted হওয়াটাই আমাদের অর্ধেক-অর্ধেক বাদ দেওয়ার অধিকার দেয়।
দেখতে সাধারণ, কিন্তু interview-তে এই একটা জিনিস bug-free লিখতে পারাটাই আসল ভিত — কারণ এর উপরেই পরের সব binary search দাঁড়াবে।
### Input ও output {#6-example-input-and-output}
```text
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 লুকায়।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো তোমার হাতে একটা মোটা dictionary, খুঁজছ "monsoon" শব্দটা। তুমি কি প্রথম পাতা থেকে এক এক করে পড়া শুরু করবে? না!
তুমি বইটা মাঝখানে খোলো — হয়তো "M" পেরিয়ে "P"-তে পড়লে। তখন পেছনের অর্ধেক পুরোটা বন্ধ করে দাও, শুধু সামনের অর্ধেকে খোঁজো। আবার সেই অর্ধেকের মাঝে খোলো। প্রতিবার অর্ধেক বই বাদ — কয়েকবারেই "monsoon"-এ পৌঁছে যাও।
dictionary sorted (alphabetical) বলেই এটা সম্ভব। এলোমেলো বইয়ে এই কৌশল খাটে না — ঠিক যেমন unsorted array-তে binary search চলে না।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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-এর সাথে প্রথম পরিচয় করছ।
### ভেতরের অঙ্ক {#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-কে এত দ্রুত বানায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
প্রথমে মাথায় আসে সবচেয়ে সরল জিনিস — **এক এক করে সব দেখা** (linear search):
```python
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, সেই দামি তথ্যটা একদম কাজে লাগায় না।
```text
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 কোন পাশে, তা নিশ্চিতভাবে জানা যায়।** তাই প্রতি ধাপে অর্ধেক ফেলে দাও।
```python
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। কিন্তু কঙ্কালটা ঠিক এটাই।
### ছবিতে বোঝা {#5-visual-explanation}
`a = [2, 5, 8, 12, 16, 23], x = 16` খুঁজছি। প্রতিটা ধাপে অর্ধেক কীভাবে মুছে যায় দেখো:
```text
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 এই বাক্যটা সত্য রাখে।
### ছোট input-এ ধাপে ধাপে {#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 নেই।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
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}
```text
lo, hi = 0, len(a) - 1
```
`lo` আর `hi` হলো search range-এর দুই সীমা — শুরুতে পুরো array (প্রথম থেকে শেষ index)।
```text
while lo <= hi:
```
যতক্ষণ range-এ অন্তত একটা element আছে (`lo <= hi`), খোঁজা চালিয়ে যাও। `lo > hi` হলে range খালি — থামো।
```text
mid = (lo + hi) // 2
```
মাঝখানের index। `// 2` integer division, তাই মাঝে দুটো element থাকলে বাঁ দিকেরটা নেয়।
```text
if a[mid] == x: return mid
```
মাঝখানেই target পেলে সরাসরি index ফেরত — কাজ শেষ।
```text
if a[mid] < x: lo = mid + 1
```
মাঝখানের মান target-এর ছোট মানে target ডান পাশে। তাই `mid` সহ বাঁ অর্ধেক বাদ — নতুন `lo` হয় `mid + 1`।
```text
else: hi = mid - 1
```
উল্টোটা — মাঝখানের মান বড়, target বাঁ পাশে। `mid` সহ ডান অর্ধেক বাদ।
বাকি `assert` গুলো নিজেদের যাচাই করছে; cross-check-এ brute force-এর সাথে প্রতিটা উত্তর মিলিয়ে দেখছি। সব ঠিক থাকলে শেষে `সব test pass!` ছাপে।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
4
-1
সব test pass!
```
প্রথম লাইন `binary_search(a, 16)` থেকে — index 4। দ্বিতীয় লাইন `binary_search(a, 10)` থেকে — 10 নেই, তাই -1। তার আগের সব `assert` (cross-check সহ) চুপচাপ pass করেছে। সবশেষে `সব test pass!` — সব ঠিক আছে।
### JavaScript ও test cases {#21-javascript-solution-with-test-cases}
JS-এ `(lo + hi) / 2` float দেয়, তাই `Math.floor` দিয়ে integer mid নিই — exact search-এ `lo <= hi` আর `mid ± 1`।
```javascript
// 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)`।
### TypeScript ও test cases {#22-typescript-solution-with-test-cases}
```typescript
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