একটি পাইথন বাইনারি অনুসন্ধান একটি সাজানো অ্যারেতে একটি আইটেমের অবস্থান খুঁজে পায়। এটি একটি তালিকাকে অর্ধেক ভাগ করে। যদি একটি নির্দিষ্ট মান মধ্যম সংখ্যার চেয়ে বেশি হয়, অনুসন্ধানটি তালিকার ডানদিকে ফোকাস করে। অন্যথায়, অনুসন্ধানটি তালিকার বাম দিকের নম্বরটি সন্ধান করে৷৷
আপনি কিভাবে একটি তালিকায় একটি আইটেমের অবস্থান খুঁজে পাবেন? বাইনারি অনুসন্ধান যে এক আপনার পিছনে আছে. বাইনারি অনুসন্ধান ব্যবহার করে, আপনি সহজেই একটি সাজানো অ্যারের ভিতরে একটি উপাদানের অবস্থান খুঁজে পেতে পারেন৷
একটি নির্দিষ্ট আইটেম খুঁজে পেতে তালিকার মাধ্যমে অনুসন্ধান করতে কম্পিউটারগুলি ভাল। তালিকায় আইটেমগুলি খুঁজে পেতে কম্পিউটারগুলি যে নিয়মগুলি ব্যবহার করে তাকে অনুসন্ধান অ্যালগরিদম বলা হয়। সবচেয়ে জনপ্রিয় পাইথন অ্যালগরিদমগুলির মধ্যে একটি হল বাইনারি অনুসন্ধান৷
৷এই নির্দেশিকায়, আমরা বাইনারি অনুসন্ধানগুলি কী এবং সেগুলি কীভাবে কাজ করে তা নিয়ে আলোচনা করতে যাচ্ছি। আমরা পাইথনে একটি বাইনারি অনুসন্ধানের একটি উদাহরণ দিয়ে হেঁটে যাবো যাতে আপনি শিখতে পারেন কিভাবে আপনার প্রোগ্রামগুলিতে একটি লিখতে হয়। চলুন শুরু করা যাক!
পাইথন বাইনারি অনুসন্ধান কি?
একটি পাইথন বাইনারি অনুসন্ধান একটি অ্যালগরিদম যা একটি অর্ডারকৃত অ্যারেতে একটি উপাদানের অবস্থান খুঁজে পায়। বাইনারি অনুসন্ধানগুলি বারবার একটি তালিকাকে দুটি ভাগে ভাগ করে। তারপর, একটি অনুসন্ধান তুলনা করে যদি একটি মান তালিকার মধ্যবর্তী মানের থেকে বেশি বা কম হয়।
আপনি একটি বাইনারি অনুসন্ধান সম্পাদন করতে পারেন দুটি উপায় আছে. উভয় পদ্ধতিই পয়েন্টার সেট করে যা একটি অ্যারের একটি নির্দিষ্ট বিন্দুতে সর্বোচ্চ এবং সর্বনিম্ন অবস্থানগুলি ট্র্যাক করতে ব্যবহৃত হয়৷
আপনি ব্যবহার করতে পারেন প্রথম পদ্ধতি হল পুনরাবৃত্তি পদ্ধতি। এই পদ্ধতিতে, অ্যারের একটি উপাদানের অবস্থান নির্ধারণ করতে বিবৃতির একটি সেট পুনরাবৃত্তি করা হয়। পাইথনে, আমরা একটি while ব্যবহার করি এই উদ্দেশ্যে লুপ।
অন্য পদ্ধতি হল পুনরাবৃত্ত পদ্ধতি। এখানেই আপনি একটি ফাংশন লিখুন যা বারবার নিজেকে কল করে যতক্ষণ না একটি তালিকার একটি উপাদান পাওয়া যায়। পুনরাবৃত্ত পদ্ধতিটি বিভাজন এবং জয় করার পদ্ধতি ব্যবহার করে যা আমরা আগে আলোচনা করেছি এবং একটি উপাদান খুঁজে না পাওয়া পর্যন্ত অনুসন্ধানের প্রক্রিয়া পুনরাবৃত্তি করে৷
81% অংশগ্রহণকারী বলেছেন যে তারা বুটক্যাম্পে যোগ দেওয়ার পরে তাদের প্রযুক্তিগত কাজের সম্ভাবনা সম্পর্কে আরও আত্মবিশ্বাসী বোধ করেছেন। আজই একটি বুটক্যাম্পের সাথে মিলিত হন৷
৷গড় বুটক্যাম্প গ্র্যাড একটি বুটক্যাম্প শুরু করা থেকে শুরু করে তাদের প্রথম চাকরি খোঁজা পর্যন্ত ক্যারিয়ারের পরিবর্তনে ছয় মাসেরও কম সময় ব্যয় করেছে।
বাইনারী অনুসন্ধান ট্রি পাইথন:ধাপে ধাপে
বিভাজন এবং বিজয় এবং পুনরাবৃত্তি সম্পর্কে যে সমস্ত কথা বলা হয়, বাইনারি অনুসন্ধান কীভাবে কাজ করে তার ট্র্যাক হারানো সহজ হতে পারে। সেই কারণে, আমরা বাইনারি অনুসন্ধান কীভাবে কাজ করে তার একটি উদাহরণে সরাসরি ঝাঁপ দিতে যাচ্ছি। নিম্নলিখিত তালিকা বিবেচনা করুন:
| 7 | 9 | 14 | 22 | 34 |
আমরা আমাদের তালিকায় "22" নম্বরটি অনুসন্ধান করতে যাচ্ছি৷
৷শুরু করার জন্য, আমরা আমাদের তালিকায় দুটি পয়েন্টার সেট করতে যাচ্ছি। একটি পয়েন্টার তালিকার সর্বোচ্চ মান প্রতিফলিত করবে, এবং অন্য পয়েন্ট সর্বনিম্ন মান প্রতিফলিত করবে:
| নিম্ন | | | | উচ্চ |
| 7 | 9 | 14 | 22 | 34 |
আমাদের পরবর্তী ধাপ হল অ্যারের মধ্যম উপাদানটি খুঁজে বের করা, যা হল 14। যদি এই মানটি আমরা যে মানের জন্য অনুসন্ধান করছি তার সমান হয়, তাহলে এই মানটি ফেরত দেওয়া উচিত।
এই ক্ষেত্রে, 14 22 এর মত নয়। তাই, আমাদের প্রোগ্রামের একটি তুলনা করা দরকার।
আমরা বর্তমান মধ্যম উপাদানের ডান দিকের উপাদানগুলির মধ্যম উপাদানটির সাথে যে সংখ্যাটির জন্য অনুসন্ধান করছি তার তুলনা করতে যাচ্ছি। যে সংখ্যাটির জন্য আমরা অনুসন্ধান করছি তা মধ্যবর্তী সংখ্যার চেয়ে বড় হলেই আমরা এটি করব। অন্যথায়, আমরা বর্তমান মধ্যম এলিমেন্টের বাম পাশের মধ্যম উপাদানটির সাথে উপাদানটির তুলনা করব।
22 নম্বরটি 14-এর থেকে বড়। আমাদের প্রোগ্রাম 22-এর সাথে আমাদের বর্তমান মধ্যম উপাদানের (14) ডান দিকের মধ্যম উপাদানের তুলনা করতে শুরু করে। এই ক্ষেত্রে, সেই সংখ্যাটি 22। এটি আমরা যে সংখ্যার জন্য অনুসন্ধান করছি তার সমান।
| | | নিম্ন | মধ্য | উচ্চ |
| 7 | 9 | 14 | 22 | 34 |
আমরা আমাদের মধ্যম মান খুঁজে পেয়েছি। আমাদের প্রোগ্রাম এখন সেই সংখ্যার সূচক অবস্থান ফেরত দেবে। এই ক্ষেত্রে, 22-এর সূচকের অবস্থান হল 3 (মনে রাখবেন, তালিকাগুলি 0 থেকে শুরু করে ইন্ডেক্স করা হয়!)।
কিভাবে পাইথনে একটি বাইনারি অনুসন্ধান প্রয়োগ করতে হয়
আসুন কিছু পাইথন কোড দিয়ে আমাদের হাত নোংরা করি। আমরা আগে আলোচনা করা উভয় পন্থা ব্যবহার করে একটি বাইনারি অনুসন্ধানের পাইথন বাস্তবায়ন অন্বেষণ করতে যাচ্ছি:পুনরাবৃত্তিমূলক এবং পুনরাবৃত্তিমূলক পদ্ধতি৷
পাইথনে পুনরাবৃত্তিমূলক বাইনারি অনুসন্ধান
আমরা পুনরাবৃত্তি পদ্ধতি দিয়ে শুরু করব। এখানেই আমরা আমাদের তালিকার প্রতিটি আইটেম লুপ করব। তারপরে, আমরা তালিকার মধ্যম মানটি খুঁজে পাব। আমরা যে মান খুঁজছি তা না পাওয়া পর্যন্ত আমরা তা করতে থাকব।
বাইনারী অনুসন্ধান ফাংশন
আমাদের বাইনারি অনুসন্ধানের জন্য একটি পাইথন ফাংশন সংজ্ঞায়িত করে শুরু করা যাক:
def findValue(numbers, number_to_find): low = 0 high = len(listnumbers - 1 while low <= high: middle = low + (high - low) // 2 if numbers[middle] == number_to_find: return middle elif numbers[middle] < number_to_find: low = middle + 1 else: high = middle - 1 return -1
আমাদের ফাংশন দুটি পরামিতি গ্রহণ করে:যে তালিকার মাধ্যমে আমরা অনুসন্ধান করতে চাই, এবং যে নম্বরটি আমরা আমাদের তালিকায় খুঁজে পেতে চাই।
তারপরে আমরা দুটি পাইথন ভেরিয়েবল ঘোষণা করেছি যা তালিকার সর্বনিম্ন এবং সর্বোচ্চ মানের জন্য ডিফল্ট মান সংরক্ষণ করে। কম 0 এ সেট করা হয়েছে, যা তালিকার শুরুর সূচক মান। উচ্চ তালিকার দৈর্ঘ্য বিয়োগ এক (কারণ তালিকাগুলি শূন্য থেকে সূচিত করা হয়েছে) সেট করা হয়েছে।
আমাদের পরবর্তী পদক্ষেপ ছিল একটি পাইথন যখন লুপ ঘোষণা করা। এই লুপটি চলে যখন সর্বনিম্ন উপাদানটি সর্বোচ্চ সংখ্যার থেকে ছোট বা সমান হয়। এর মানে হল যে আমাদের লুপ তখনই চলবে যদি আমাদের নম্বর এখনও পাওয়া না যায়।
তারপর, আমরা মাঝের সংখ্যা গণনা করি। আমরা সর্বোচ্চ মান থেকে সর্বনিম্ন মান বিয়োগ করে এটি করি। তারপরে 2 দ্বারা ভাগ করলে আমরা সেই সংখ্যাটির মডুলো (অবশিষ্ট) গণনা করি। তারপর, আমরা সর্বনিম্ন সংখ্যার মানের সাথে মডিউল যোগ করি।
যদি আমাদের তালিকার মাঝের সংখ্যাটি আমরা যে নম্বরটি খুঁজে পেতে চাই তার সমান হয়, আমরা সেই সংখ্যাটির অবস্থান ফিরিয়ে দিই৷
আমরা আমাদের নতুন "নিম্ন" সংখ্যাটি মধ্যম অবস্থানের থেকে একটি বড়ের সমান সেট করেছি৷ মাঝামাঝি সংখ্যাটি আমরা যে সংখ্যাটি খুঁজে পেতে চাই তার চেয়ে কম হলে এটি ঘটে। এটি আমাদের অনুসন্ধানকে আমাদের তালিকার বাম দিকে নিয়ে যায়, যেমন আমরা আগে আমাদের ভিজ্যুয়াল উদাহরণে করেছি৷
অন্যথায়, আমরা আমাদের "উচ্চ" সংখ্যাটি মধ্যম অবস্থানের থেকে একটি কমের সমান সেট করি। এটি আমাদের অনুসন্ধানকে আমাদের তালিকার ডানদিকে নিয়ে যায়৷
নিম্ন সমান বা উচ্চ থেকে কম না হওয়া পর্যন্ত এটি পুনরাবৃত্তি হয়। যদি আমাদের মান পাওয়া না যায়, আমরা -1 ফেরত দিই। আমরা এক মিনিটের মধ্যে কেন তা নিয়ে কথা বলব৷
৷অনুসন্ধান চালান
findValue-এর বাইরে, আপনার প্রোগ্রামের নীচে নিচের কোডটি যোগ করুন ফাংশন:
numbers = [7, 9, 14, 22, 34]
number_to_find = 22
final = findValue(numbers, number_to_find)
if final == -1:
print("This item was not found in the list.")
else:
print("The number " + str(number_to_find) + " was found at index position " + str(final) + ".")
আমরা যে আইটেমগুলির মাধ্যমে অনুসন্ধান করতে চাই তার তালিকা ঘোষণা করে শুরু করেছি। তারপরে আমরা যে নম্বরটি খুঁজে পেতে চাই তা নির্দিষ্ট করেছি, যা 22।
এরপর, আমরা আমাদের findValue() কল করি ফাংশন এবং এটির মাধ্যমে তালিকা পাস করুন।
এখানে -1 আগে থেকে আসে। যদি আমাদের ফাংশন দ্বারা প্রত্যাবর্তিত সংখ্যা -1 হয়, তার মানে হল যে আমাদের আইটেমটি তালিকায় পাওয়া যায়নি। প্রোগ্রামাররা প্রায়ই এই ধরনের পরিস্থিতিতে -1 ব্যবহার করে কারণ আমাদের অনুসন্ধান ফাংশন একটি নেতিবাচক সংখ্যা ফেরত দিতে পারে না।
অন্যথায়, আমাদের প্রোগ্রাম একটি বার্তা প্রিন্ট করে যা আমাদের সেই মানের সূচক অবস্থান জানায়।
আমাদের কোড ফিরে আসে:
The number 22 was found at index position 3.
এখন আমরা জানি যে 22 নম্বরটি ইনডেক্স পজিশন 3 এ উপস্থিত হয়।
পাইথনে পুনরাবৃত্ত বাইনারি অনুসন্ধান
আমরা একটি বাইনারি অনুসন্ধান সম্পাদন করতে পুনরাবৃত্তি ব্যবহার করতে পারি। এখানেই আমরা একটি ফাংশন সংজ্ঞায়িত করব যা একটি শর্ত - আমাদের নম্বর পাওয়া যাওয়া - পূরণ না হওয়া পর্যন্ত নিজেকে কল করতে থাকে৷
একটি পুনরাবৃত্ত ফাংশন সংজ্ঞায়িত করুন
আমাদের শেষ উদাহরণের মতো, আমরা একটি ফাংশন লিখে শুরু করব যা আমাদের বাইনারি অনুসন্ধান সম্পাদন করে:
def findValue(numbers, number_to_find, low, high): if high >= low: middle = low + (high - low) // 2 if numbers[middle] == number_to_find: return middle elif numbers[middle] < number_to_find: return findValue(numbers, number_to_find, middle + 1, high) else: return findValue(numbers, number_to_find, low, middle - 1) else: return -1
আমাদের কোড আমাদের শেষ উদাহরণের সাথে কিছুটা মিল রয়েছে৷
৷আমরা সর্বোচ্চ মান কমের চেয়ে বড় বা সমান কিনা তা পরীক্ষা করে শুরু করি। যদি এটি হয়, আমাদের প্রোগ্রাম ফিরে আসবে -1. অন্যথায়, এটি একটি বাইনারি অনুসন্ধান সম্পাদন করা শুরু করবে৷
৷আমরা শেষ উদাহরণের মতো একই পদ্ধতি ব্যবহার করে মধ্যম সংখ্যা গণনা করি। প্রথমত, আমরা সর্বোচ্চ মান থেকে সর্বনিম্ন বিয়োগ করি। তারপর, 2 দ্বারা ভাগ করলে আমরা সেই মানের মডিউল (বাকি) গণনা করি। অবশেষে, আমরা সর্বনিম্ন সংখ্যা যোগ করি।
আমরা তখন একটি if লিখেছি বিবৃতি যা আমাদের বাইনারি অনুসন্ধান কিভাবে এগিয়ে যেতে হবে তা নির্ধারণ করে:
- যদি মধ্যবর্তী সংখ্যাটি আমরা যেটি খুঁজছি তার সমান হয়, তাহলে সেই সংখ্যাটির অবস্থান ফেরত দেওয়া হবে।
- যদি মধ্যবর্তী সংখ্যাটি আমরা খুঁজছি তার চেয়ে কম হয়, আমাদের findValue() ফাংশন আবার বলা হয়। এইবার, কম এর মান আমাদের মধ্যম মানের চেয়ে বড় একটি সমান হতে সেট করা হয়েছে৷
- যদি মধ্যম সংখ্যাটি আমরা খুঁজছি তার চেয়ে বড় হয়, findValue() ফাংশন বলা হয়। "উচ্চ" এর মান মধ্যম মানের থেকে এক কমের সমান হবে।
প্রধান প্রোগ্রাম লিখুন
আমাদের যা করতে বাকি আছে তা হল আমাদের মূল প্রোগ্রাম লিখুন:
numbers = [7, 9, 14, 22, 34]
number_to_find = 22
final = findValue(numbers, number_to_find, 0, len(numbers) - 1)
if final == -1:
print("This item was not found in the list.")
else:
print("The number " + str(number_to_find) + " was found at index position " + str(final) + ".")
আমাদের প্রধান প্রোগ্রাম আমাদের আগের উদাহরণ বার এক পার্থক্য হিসাবে একই. আমরা আমাদের findValue()-এ দুটি নতুন প্যারামিটার পাস করছি ফাংশন:নিম্ন এবং উচ্চ।
আমাদের এটি করতে হবে কারণ আমাদের অ্যালগরিদম পুনরাবৃত্তিমূলক, এবং আমরা আমাদের ফাংশনে সেই মানগুলি বরাদ্দ করতে পারি না। যদি আমরা আমাদের ফাংশনে মানগুলি বরাদ্দ করি, তবে প্রতিবার আমাদের ফাংশন চালানোর সময় সেই মানগুলি পুনরায় সেট করা হবে, যা আমাদের অনুসন্ধান অ্যালগরিদমকে ভেঙে দেবে৷
আমাদের কোড ফিরে আসে:
The number 22 was found at index position 3.
আমরা আগের থেকে একই ফলাফল পেয়েছি। এই উদাহরণে, আমরা আমাদের বাইনারি অনুসন্ধান সম্পাদন করতে একটি পুনরাবৃত্তিমূলক প্রোগ্রামের পরিবর্তে একটি পুনরাবৃত্ত প্রোগ্রাম ব্যবহার করেছি৷
আপনি কখন একটি পাইথন বাইনারি অনুসন্ধান ব্যবহার করবেন?
একটি বাইনারি অনুসন্ধান হল সংখ্যার তালিকার মাধ্যমে অনুসন্ধান করার একটি কার্যকর উপায়। এই অনুসন্ধান একটি রৈখিক অনুসন্ধানের চেয়ে আরও দক্ষ। এর কারণ হল বাইনারি পদ্ধতি আপনার অনুসন্ধানকে অর্ধেকে কমিয়ে দেয় যত তাড়াতাড়ি আপনি একটি সাজানো তালিকার মাঝখানে খুঁজে পান।
এটি মনে রাখা গুরুত্বপূর্ণ যে একটি তালিকাকে বাইনারি অনুসন্ধান ব্যবহার করে অনুসন্ধান করার আগে সংখ্যাগতভাবে অর্ডার করতে হবে। আপনি একটি বাইনারি অনুসন্ধান সম্পাদন করার আগে, নিশ্চিত করুন যে আপনার সংখ্যাগুলি আরোহী ক্রমে সাজানো হয়েছে৷
৷পাইথন জটিলতা ব্রেকডাউনে বাইনারি অনুসন্ধান
বাইনারি অনুসন্ধানের জটিলতা কী? এটা একটা ভালো প্রশ্ন।
বাইনারি অনুসন্ধান অ্যালগরিদমে O(1) এর একটি সেরা কেস জটিলতা রয়েছে। এটি ঘটে যখন প্রথম তুলনাটি আপনি যে আইটেমটির জন্য অনুসন্ধান করছেন তার সমান হয়৷
৷বাইনারি অনুসন্ধানের জন্য গড় এবং সবচেয়ে খারাপ ক্ষেত্রে জটিলতা হল O(log n)। এর মানে হল যে একটি তালিকায় কতগুলি আইটেম অনুসন্ধান করতে হবে তার উপর নির্ভর করে একটি অনুসন্ধান পরিচালনা করতে যে সময় লাগে তা লগারিদমিকভাবে বৃদ্ধি পায়৷
উপসংহার
বাইনারি অনুসন্ধান একটি তালিকায় একটি মানের সূচক অবস্থান খুঁজে বের করার একটি কার্যকর উপায়৷
প্রতিবার বাইনারি অনুসন্ধান চালানো হলে, অনুসন্ধানটি তালিকাটিকে দুটি ভাগে ভাগ করবে। আপনি যে নম্বরটির জন্য অনুসন্ধান করছেন তার কাছাকাছি তালিকার পাশে অনুসন্ধানটি ফোকাস করে৷
প্রতিবার অনুসন্ধান চালানোর জন্য, প্রোগ্রামটিকে যে সংখ্যার মাধ্যমে অনুসন্ধান করতে হবে তার পরিমাণ অর্ধেক হয়ে যায়৷
পাইথন সম্পর্কে আরও জানতে, আমাদের পাইথন কীভাবে শিখবেন নির্দেশিকা পড়ুন।
