DSA: 2 | Binary Search Algorithms in Bangla | বাইনারি সার্চ অ্যালগরিদম
All You need to learn to Begin with Binary Search
Hi, I’m Ibrahim Sifat, a Frontend Engineer and Full Stack Developer based in Jeddah, Saudi Arabia. I specialize in building scalable web applications with React, Next.js, and Laravel. With over 4 years of experience, I love creating user-friendly designs, optimizing performance, and solving complex problems. Let’s build something great together!
Quick Note
আমি একজন learner। যেভাবে আমি concept টা understand করেছি, সেভাবেই explain করার try করেছি। So... এই journey তে কোন mistake দেখলে, বা কিছু add করার থাকলে, কোন জায়গায় বুঝতে problem হলে, যেকোনো সময় comment করে জানাতে পারেন। একসাথে learning টা more enjoyable হবে!
Since I'm not a pro (এখনো শিখছি!), there might be some mistakes. আপনাদের feedback আমার কাছে valuable হবে!
Let's learn and grow together! চলোন শুরু করি! 🚀
Recap
গত ক্লাসে আমরা Linear Search নিয়ে কথা বলেছিলাম, যেখানে আমরা একটা একটা করে সব element চেক করতাম। কিন্তু আজ? আজ আমরা শিখবো একটা অনেক স্মার্ট টেকনিক - Binary Search!
Binary Search কি? 🤔
ধরো, আপনার বন্ধু সৌরভ তার বার্থডে তে তোমাকে দাওয়াত দিয়েছে। কিন্তু ওপস! তুমি ওর ফ্ল্যাট নাম্বার ভুলে গেছো। তুমি জানো এটা ১-১০০ এর মধ্যে। এখন কি করবে?
Approach 1: নিউবি স্টাইল 🐌
১ নাম্বার ফ্ল্যাটে নক করো
নাহ, এটা না
২ নাম্বারে যাও
এটাও না
৩... ৪... ৫... (হাঁফিয়ে উঠলে😓)
Approach 2: স্মার্ট স্টাইল 🚀
প্রথমে ৫০ নাম্বার ফ্ল্যাটে যাও
সৌরভের ফ্ল্যাট ৭৫ নাম্বার? ওকে, তাহলে ৫১-১০০ এর দিকে যাই
৭৫ চেক করি... এরপর ৮৮... তারপর ৮২
এভাবে খুব তাড়াতাড়ি পৌঁছে যাবে!
Seconde Example:
কল্পনা করুন, আপনি একটি লাইব্রেরিতে একটি বই খুঁজছেন। লাইব্রেরিতে হাজার হাজার বই আছে, কিন্তু সৌভাগ্যবশত সেগুলি alphabetically সাজানো। এখন, আপনি কি প্রতিটি বই একে একে চেক করবেন? না, আপনি মাঝখানে গিয়ে দেখবেন, তারপর সিদ্ধান্ত নেবেন আপনার বইটি ডানে না বামে। এটাই হলো Binary Search এর মূল concept।
ধরুন আপনার বন্ধু ১ থেকে ১০০ এর মধ্যে একটি নাম্বার মনে করেছে। আপনাকে সেই নাম্বারটি guess করতে হবে। কিভাবে করবেন?
Inefficient approach: ১ থেকে শুরু করে একে একে সব নাম্বার guess করা
অন্য দিকেঃ Efficient approach (Binary Search):
প্রথমে ৫০ guess করা
যদি নাম্বারটি ৫০ এর চেয়ে বড় হয়, তবে ৫১-১০০ এর মধ্যে খোঁজা
যদি ছোট হয়, তবে ১-৪৯ এর মধ্যে খোঁজা
এভাবে range কে ধাপে ধাপে অর্ধেক করে কমিয়ে আনা
Binary Search এর মূলনীতি
Binary Search এর মূল কথা হলো "Divide and Conquer"। প্রতিবার সার্চ স্পেস কে দুই ভাগে ভাগ করে, আমরা ঠিক করি কোন দিকে যাবো।
1. Pre-requisites
Sorted Data: ডাটা অবশ্যই সাজানো থাকতে হবে
Phone Contacts: A থেকে Z
Numbers: ছোট থেকে বড় বা বড় থেকে ছোট
Dates: পুরনো থেকে নতুন বা নতুন থেকে পুরনো
2. Search Space
প্রতিবার সার্চ স্পেস অর্ধেক হয়
- ১০০টা জিনিস -> ৫০টা -> ২৫টা -> ১৩টা -> ৭টা -> ৪টা -> ২টা -> ১টা
এভাবে খুব দ্রুত টার্গেট পাওয়া যায়
3. Decision Making
প্রতি ধাপে তিনটা সম্ভাবনা:
Found: টার্গেট পেয়ে গেছি! 🎉
Go Left: টার্গেট ছোট, বাম দিকে যাই ⬅️
Go Right: টার্গেট বড়, ডান দিকে যাই ➡️
Why Binary Search is Amazing?
1. Speed Comparison
ধরো, ১০২৪টা জিনিস আছে:
Linear Search: সর্বোচ্চ ১০২৪ বার চেক
Binary Search: মাত্র ১০ বার! (2¹⁰ = 1024)
2. Real-world Benefits
Google Search suggestion
Auto-complete features
Database queries
Finding bugs in code (git bisect)
এখানেঃ
প্রথম স্টেপ:
পুরো অ্যারে দেখি
মাঝের এলিমেন্ট = 40
60 বড় হওয়ায় ডান দিকে যাই
দ্বিতীয় স্টেপ:
শুধু ডান অংশ দেখি (50, 60, 70)
নতুন মাঝের এলিমেন্ট = 60
টার্গেট পেয়ে গেছি!
শেষ স্টেপ:
60 পাওয়া গেছে
সার্চ শেষ!
Before We Code...
Mental Model টৈরি করি:
Divide: অর্ধেক করে ভাগ করো
Compare: মাঝের element এর সাথে compare করো
Conquer: যে দিকে target, সেদিকে যাও
Repeat: টার্গেট না পাওয়া পর্যন্ত repeat করো
Pseudo-code!
চলো এবার দেখি কিভাবে এটা কোড করা যায়:
Algorithm: BinarySearch
// ইনপুট হিসেবে একটি sorted array এবং খোঁজার target value নিবে
Input: sorted_array, target_value
// আউটপুট হিসেবে target এর position অথবা না পেলে -1 রিটার্ন করবে
Output: index of target_value or -1 if not found
Begin
// বাম দিক থেকে শুরু করব, তাই left = 0
set left = 0
// ডান দিকের শেষ position (array এর length - 1)
set right = length of sorted_array - 1
// যতক্ষণ left right এর চেয়ে ছোট বা সমান থাকবে, ততক্ষণ লুপ চলবে
while left <= right do
// middle position বের করি
// (right - left) / 2 করার কারণ: বড় নাম্বারের ক্ষেত্রে overflow এড়ানো
set mid = left + (right - left) / 2
// দেখি middle position এ আমাদের target আছে কিনা
if sorted_array[mid] equals target_value then
// target পেয়ে গেছি, এর position রিটার্ন করি
return mid
// যদি middle এর value target এর চেয়ে ছোট হয়
// তাহলে target ডান দিকে আছে
else if sorted_array[mid] < target_value then
// left কে mid এর পরের position এ নিয়ে যাই
set left = mid + 1
// যদি middle এর value target এর চেয়ে বড় হয়
// তাহলে target বাম দিকে আছে
else
// right কে mid এর আগের position এ নিয়ে যাই
set right = mid - 1
end while
// এখানে আসার মানে target পাওয়া যায়নি
// তাই -1 রিটার্ন করি
return -1
End
আরও কিছু গুরুত্বপূর্ণ নোট:
left <= right: এই condition না দিলে কিছু ক্ষেত্রে target miss করতে পারিmid + 1এবংmid - 1: এই ১ যোগ/বিয়োগ না করলে infinite loop হতে পারেleft + (right - left) / 2: এভাবে লেখার কারণ হল integer overflow এড়ানো-1return: array তে element না থাকলে -1 return করি (programming এ এটা standard practice)
চলো Line by Line বুঝি 🔍
১. Initialize করা:
Copyset left = 0
set right = length of sorted_array - 1
leftহচ্ছে আমাদের বাম দিকের সীমানাrightহচ্ছে ডান দিকের সীমানাপ্রথমে পুরো array কে consider করি
২. Middle Point ক্যালকুলেশন:
Copyset mid = left + (right - left) / 2
Special Note: আমরা (left + right) / 2 না লিখে left + (right - left) / 2 লিখি কেন?
- Integer Overflow এড়াতে! বড় নাম্বার নিয়ে কাজ করার সময় এটা খুব important
আচ্ছা, চলুন mid = left + (right - left) / 2 এর পুরো বিষয়টা খুব সহজ করে বুঝি।
প্রথমে বুঝি - আমরা mid কেন দুইভাবে লিখতে পারি:
mid = (left + right) / 2mid = left + (right - left) / 2
ধরি, আমাদের array তে ৫টা এলিমেন্ট আছে:
index: 0 1 2 3 4
value: [10, 20, 30, 40, 50]
এখন,
left = 0
right = 4
পদ্ধতি ১: (left + right) / 2
mid = (0 + 4) / 2
= 4 / 2
= 2
পদ্ধতি ২: left + (right - left) / 2
mid = 0 + (4 - 0) / 2
= 0 + 4 / 2
= 0 + 2
= 2
দুইটা পদ্ধতিতেই একই উত্তর পেলাম। তাহলে দ্বিতীয় পদ্ধতি কেন ব্যবহার করি?
The Integer Overflow Problem
আসুন একটা বড় array নিয়ে চিন্তা করি:
left = 2,000,000,000
right = 2,000,000,100
পদ্ধতি ১: (left + right) / 2
mid = (2,000,000,000 + 2,000,000,100) / 2
= 4,000,000,100 / 2
❌ PROBLEM! 4,000,000,100 is too big for integer!
পদ্ধতি ২: left + (right - left) / 2
mid = 2,000,000,000 + (2,000,000,100 - 2,000,000,000) / 2
= 2,000,000,000 + 100 / 2
= 2,000,000,000 + 50
= 2,000,000,050
✅ WORKS PERFECTLY!
Summary:
ছোট নাম্বারের ক্ষেত্রে দুইটা পদ্ধতিই কাজ করে
কিন্তু বড় নাম্বারের ক্ষেত্রে:
(left + right)overflow করতে পারে(right - left)কখনোই overflow করবে না (কারণ এটা always positive difference)
তাই সব সময় left + (right - left) / 2 ব্যবহার করা best practice!
৩. তিনটি কেস হ্যান্ডলিং:
Copyif sorted_array[mid] equals target_value then
return mid
else if sorted_array[mid] < target_value then
set left = mid + 1
else
set right = mid - 1
Case 1: Bulls eye! টার্গেট পেয়ে গেছি
Case 2: টার্গেট বড়, ডানে যাও
Case 3: টার্গেট ছোট, বামে যাও
Time Complexity Analysis
Best Case: O(1) - একদম প্রথমেই পেয়ে গেলাম!
Average Case: O(log n) - প্রতিবার অর্ধেক করে কমছে
Worst Case: O(log n) - শেষ পর্যন্ত খুঁজতে হলো
একটু ম্যাথ করি:
১০২৪ টা এলিমেন্ট থাকলে:
Linear Search: সর্বোচ্চ ১০২৪ বার চেক
Binary Search: মাত্র ১০ বার চেক! (2¹⁰ = 1024)
Common Mistakes to Avoid
Unsorted Array: বাইনারি সার্চ শুধু sorted array তেই কাজ করে
Infinite Loop:
midক্যালকুলেশনে ভুল করলে হতে পারেWrong Boundary Updates:
left = midবাright = midব্যবহার - এটা infinite loop create করতে পারে
Tips
নিজে নিজে ট্রেস করো:
একটা ছোট array নাও
প্রতি step এ
left,mid,rightএর value লিখোকিভাবে search space কমছে তা observe করো
Edge Cases চেক করো:
Empty array
Single element array
Target not in the array
Duplicate elements
Target at boundaries
Binary Search vs Linear Search: A Deep Dive 🔍
In This Section we will learn:
দুটি সার্চ এর মূল পার্থক্য
Time & Space Complexity বিশ্লেষণ
বাস্তব জীবনে এদের ব্যবহার
🔴 লিনিয়ার সার্চ:
একে একে প্রতিটি এলিমেন্ট চেক করে
৬টি ধাপে টার্গেট পায়
🟢 বাইনারি সার্চ:
মাঝখান থেকে শুরু করে
মাত্র ২টি ধাপে টার্গেট পায়
বাইনারি সার্চের সুবিধা
দ্রুত খুঁজে পায়
কম স্টেপ লাগে
বড় ডাটা সেটে অনেক এফিসিয়েন্ট
দুটি সার্চের Main পার্থক্য
Memory Access Pattern
Linear Search:
CopyMemory Access: [1] -> [2] -> [3] -> [4] -> [5] -> [6]
Sequential প্যাটার্নে মেমরি অ্যাক্সেস
Binary Search:
CopyMemory Access: [4] -> [2] -> [3] অথবা [4] -> [6] -> [5]
Jump করে করে মেমরি অ্যাক্সেস
Cache Performance
Linear Search:
Cache-friendly (পাশাপাশি মেমরি লোকেশন অ্যাক্সেস করে)
CPU Prefetcher ভালোভাবে কাজ করে
ছোট ডাটাসেটে বেশি efficient
Binary Search:
Cache-unfriendly (রেন্ডম মেমরি লোকেশন অ্যাক্সেস করে)
CPU Prefetcher কম effective
বড় ডাটাসেটে এই overhead negligible
ধরো, আপনার দুই বন্ধু আছে - লিটু (Linear Search) আর বিটু (Binary Search)। তাদের একটা চ্যালেঞ্জ দেওয়া হলো: লাইব্রেরির ১০০টা বই থেকে "ডাটা স্ট্রাকচার" নামের বইটা খুঁজে বের করতে হবে। বইগুলো A-Z অনুযায়ী সাজানো।
লিটুর পদ্ধতি (Linear Search):
লিটু: "আমি প্রথম বই থেকে শুরু করব!"
- "অ্যালগরিদম" - নাহ, এটা না
- "আর্টিফিশিয়াল ইন্টেলিজেন্স" - এটাও না
- "ইন্টারনেট" - না...
[একে একে প্রতিটা বই চেক করতে থাকে]
বিটুর পদ্ধতি (Binary Search):
বিটু: "আমি স্মার্টলি খুঁজব!"
- মাঝের বই দেখে ('ম' দিয়ে শুরু) - "ড" আগে আসে
- এবার প্রথম অর্ধেকের মাঝে ('চ' দিয়ে শুরু) - "ড" পরে আসে
- "চ" এবং "ম" এর মাঝামাঝি...
[দ্রুত "ডাটা স্ট্রাকচার" পেয়ে যায়]
কে কত দ্রুত?
সময়ের খেলা
ধরো, প্রতি বই চেক করতে ১ সেকেন্ড লাগে:
লিটুর কেস:
ভাগ্য ভালো হলে (Best Case):
- প্রথমেই বই পেয়ে গেল
- মাত্র ১ সেকেন্ড!
ভাগ্য খারাপ হলে (Worst Case):
- শেষের দিকে বা একদম শেষে বই
- ১০০ সেকেন্ড
গড় ক্ষেত্রে (Average Case):
- মাঝামাঝি কোথাও বই
- ৫০ সেকেন্ড
বিটুর কেস:
সব ক্ষেত্রেই (Best, Average, Worst):
- প্রতিবার অর্ধেক জায়গা চেক করে
- ১০০ টা বইয়ের জন্য মাত্র ৭ বার চেক! (log₂100 ≈ 7)
- মাত্র ৭ সেকেন্ড! 🚀
🧠 মেমরি Managment
লিটুর মেমরি (Space Complexity: O(1))
শুধু একটা variable লাগে:
- বর্তমান position track করার জন্য
বিটুর মেমরি (Space Complexity: O(1))
তিনটা variable লাগে:
- left position
- right position
- middle position
Binary Search Performance Analysis
বাইনারি সার্চের Performance:
ধরি আমার কাছে ১-১০০ এর মধ্যে একটা নাম্বার আছে। আপনি কিভাবে খুঁজবেন?
পদ্ধতি ১: Linear Search
CopyPlayer: 1 কি?
Me: না, বড়
Player: 2 কি?
Me: না, বড়
Player: 3 কি?
Me: না, বড়
[এভাবে চলতে থাকবে... 😫]
পদ্ধতি ২: Binary Search
CopyPlayer: 50 কি?
Me: না, বড়
Player: 75 কি?
Me: না, ছোট
Player: 62 কি?
Me: হ্যাঁ! 🎉
Performance
1. Best Case
Copyখেলা: "১-১০০ এর মধ্যে একটা নাম্বার ধরি"
নাম্বার: 50
First Guess: 50
Bingo! একবারেই পেয়ে গেলাম!
2. Average Case
Copyখেলা: "১-১০০ এর মধ্যে একটা নাম্বার ধরি"
নাম্বার: 75
Guess 1: 50 (না, বড় হবে)
Guess 2: 75 (পেয়ে গেছি!)
3. Worst Case
Copyখেলা: "১-১০০ এর মধ্যে একটা নাম্বার ধরি"
নাম্বার: 99
Guess 1: 50 (না, বড় হবে)
Guess 2: 75 (না, বড় হবে)
Guess 3: 87 (না, বড় হবে)
Guess 4: 93 (না, বড় হবে)
Guess 5: 99 (পেয়ে গেছি!)
Remember
Binary Search সব সময় দ্রুত, কিন্তু ডাটা সাজানো লাগবে
যত বড় ডাটা, Binary Search তত বেশি এফিশিেন্ট
১০০০ টা জিনিস খুঁজতে মাত্র ১০ বার চেক!
Order-Agnostic Binary Search Flow
বিস্তারিত :
1. Start Node (সবুজ সার্কেল)
এটি আমাদের algorithm এর শুরু
এখান থেকে আমরা array input নিয়ে কাজ শুরু করব
2. Order Detection Box (নীল রেক্টাংগেল)
Copy- Input Array: [a1, a2, ..., an]
- Check: a1 vs an
- Purpose: Determine if ascending or descending
3. Decision Diamond (লাল ডায়মন্ড)
কন্ডিশন:
arr[0] < arr[last]দুইটি সম্ভাব্য পথ:
Yes (Left) -> Ascending
No (Right) -> Descending
4. Order Boxes
CopyAscending (সবুজ):
- উদাহরণ: [1, 2, 3, 4, 5]
- Property: প্রতিটি element আগেরটার চেয়ে বড়
Descending (কমলা):
- উদাহরণ: [5, 4, 3, 2, 1]
- Property: প্রতিটি element আগেরটার চেয়ে ছোট
5. Search Logic Box (বেগুনি)
Modified comparisons based on order
Binary Search implementation with order consideration
Search Process Comparison
Comparison Logic Table
CopyAscending Order:
IF target < mid THEN go left
IF target > mid THEN go right
Descending Order:
IF target < mid THEN go right
IF target > mid THEN go left
Decision Tree
বিস্তারিত :
1. Root Node (টপ নোড)
CopyPurpose: Order Detection
Check: arr[0] vs arr[last]
Example:
- arr[0] = 5, arr[last] = 1 -> Descending
- arr[0] = 1, arr[last] = 5 -> Ascending
2. First Level
CopyLeft Node (Ascending):
- When: arr[0] < arr[last]
- Example: [1, 2, 3, 4, 5]
Right Node (Descending):
- When: arr[0] > arr[last]
- Example: [5, 4, 3, 2, 1]
3. Second Level
CopyAscending Branch:
- Left Child: When target < mid
- Right Child: When target > mid
Descending Branch:
- Left Child: When target > mid
- Right Child: When target < mid
Digit Operations: ডিজিট অপারেশন পরিচিতি 🔍
Basic Digit Extraction (ডিজিট বের করা)
ডিজিট এক্সট্রাকশন :
CopyLast Digit: num % 10
Remove Last Digit: num / 10
উদাহরণ:
CopyNumber = 12345
Step 1: 12345 % 10 = 5
Step 2: 12345 / 10 = 1234
Step 3: 1234 % 10 = 4
Step 4: 1234 / 10 = 123
...এভাবে চলতে থাকবে
চলুন কয়েকটা কোড স্ট্রাকচার দেখি
সাধারণ ডিজিট এক্সট্রাকশন:
CopyAlgorithm: ExtractDigits
Input: number (An integer)
Output: Array of digits
Begin
digits = empty array
while number > 0 do
digit = number % 10
add digit to start of digits
number = number / 10
end while
return digits
End
রিভার্স নাম্বার তৈরি:
CopyAlgorithm: ReverseNumber
Input: number
Output: Reversed number
Begin
reversed = 0
while number > 0 do
digit = number % 10
reversed = (reversed * 10) + digit
number = number / 10
end while
return reversed
End
Let me explain Memory Representation in depth for digit operations.
ডিজিট অপারেশনে মেমরি রেপ্রেজেন্টেশন 🧠
মেমরি টাইপস Types of Memory
স্ট্যাক মেমরি Stack Memory
- প্রাইমারি ভ্যারিয়েবলস স্টোর করে
- LIFO (Last In First Out) প্রিন্সিপাল
- অটোমেটিক মেমরি ম্যানেজমেন্ট
Example:
int number = 12345; // স্ট্যাকে 4 বাইট নেয়
int digit; // আরও 4 বাইট স্ট্যাকে
int sum = 0; // আরও 4 বাইট স্ট্যাকে
হিপ মেমরি Heap Memory
- ডায়নামিক অ্যারে স্টোর করে
- ম্যানুয়াল মেমরি ম্যানেজমেন্ট
- বড় ডাটা স্ট্রাকচার স্টোর করার জন্য
ডিজিট স্টোরেজ প্যাটার্ন
সিঙ্গেল ডিজিট স্টোরেজ
32-bit Integer Memory Layout:
[Byte 3][Byte 2][Byte 1][Byte 0]
একটি ডিজিট (0-9) স্টোর করার জন্য:
- মাত্র 4 বিট প্রয়োজন (0000 to 1001)
- কিন্তু 1 বাইট (8 বিট) ব্যবহার করা হয়
- বাকি বিটগুলো 0 দিয়ে পূরণ করা হয়
মাল্টি-ডিজিট নাম্বার স্টোরেজ
Example: 12345
Memory Layout:
[00000000][00000000][00110000][00111001]
Memory Operations মেমরি অপারেশনস
Digit Extraction Process ডিজিট এক্সট্রাকশন প্রসেস
Step 1: Original Number (12345)
Memory: [00000000][00000000][00110000][00111001]
Step 2: Get Last Digit (12345 % 10 = 5)
- Modulo Operation
- Register Operation
- Result in New Memory Location
Step 3: Remove Last Digit (12345 / 10 = 1234)
- Division Operation
- Bit Shifting
- Update Original Memory
অ্যারে স্টোরেজ
int[] digits = new int[5]; // Heap Memory Allocation
Memory Layout:
[1][2][3][4][5]
↓ ↓ ↓ ↓ ↓
0xA1 0xA2 0xA3 0xA4 0xA5 (Memory Addresses)
মেমরি অপটিমাইজেশন টেকনিক 🎯
ইন-প্লেস অপারেশন
// Bad Practice (Extra Memory)
int temp = number;
while (temp > 0) {
digit = temp % 10;
temp /= 10;
}
// Good Practice (In-place)
while (number > 0) {
digit = number % 10;
number /= 10;
}
বাইনারি সার্চ শেখার এই যাত্রায় আমরা অনেক কিছুই জানলাম। শুরু করেছিলাম সাধারণ বাইনারি সার্চ দিয়ে দেখলাম কিভাবে একটি সিম্পল algorithm আমাদের দৈনন্দিন প্রোগ্রামিং life কে সহজ করে দিতে পারে।
Key Takeaways
বাইনারি সার্চ হল একটি efficient searching technique
এটি log(n) টাইম কমপ্লেক্সিটিতে কাজ করে
Sorted array তে খোঁজার জন্য এটি best choice
Order-Agnostic version যেকোনো order এ কাজ করে
"The more you practice, the more patterns you'll recognize!"
Happy Coding! See you in the next time!
#DSA #BinarySearch #Programming #CodingLife #ProblemSolving
