লিনিয়ার সার্চ (Linear Search)

সার্চিং অ্যালগরিদমের মধ্যে সব চেয়ে সহজ অ্যালগরিদম হল লিনিয়ার সার্চ (Linear search)। নাম দেখেই বুঝতে পারছো এই অ্যালগরিদম কিভাবে সার্চ করে। লিনিয়ার সার্চ মানে সরল রৈখিকভাবে খোঁজা। ধরো তুমি তোমার বিশ্ববিদ্যালয়ের লাইব্রেরি থেকে কোরেমনের লেখা “Introduction to algorithm” বইটি খুঁজে বের করবে। তোমার বিশ্ববিদ্যালয়ের লাইব্রেরিতে প্রায় ৩ হাজার বই আছে। তোমার জানা নেই বইটি বুক সেলফের কোন যায়গায় আছে। এখন তুমি কি করবে? তুমি যদি এলোমেলোভাবে খোঁজো তাহলে বইটি পেতেও পারো আবার না পেতেও পারো। কিন্তু তুমি যদি বুক সেলফের এক প্রান্ত থেকে খুঁজতে শুরু করে শেষ প্রান্ত পর্যন্ত খোঁজো, তাহলে নিশ্চিত ভাবে বলা যায় বইটি লাব্রেরিতে থাকলে তুমি অবশ্যই পাবে। এটাই হল linier search প্রক্রিয়া।

এখন তোমাকে কিছু সংখ্যার একটি লিস্ট দেওয়া হল । লিস্টটি এইরকম-   

13

36

8

45

52

19

136

76

তোমাকে বলা হল এই লিস্টের মাঝে 45 সংখ্যাটি আছে কিনা খুঁজে বের করো। তুমি বাম থেকে ডানে অথবা ডান থেকে বামে একটার পর একটা সংখ্যা খুঁজে দেখলে 45 সংখ্যাটি এই লিস্টে আছে। এখন তোমাকে বলা হল সংখ্যাটি লিস্টের বাম দিক থেকে কত নম্বর পজিশনে আছে। তুমি হয়ত অতি উৎসাহে বলে দিবে ৪ নম্বর পজিশনে আছে !  যদি এই পর্যন্ত বুঝতে পারো তাহলে বলতে পারি লিনিয়ার সার্চ অ্যালগরিদম তুমি বুঝে গেছো। এখন এই প্রক্রিয়াটিকে আমরা সি প্রোগ্রামিংয়ের সাহায্যে প্রকাশ করব।

তুমি দেখতে পাচ্ছ এখানে আটটি সংখ্যার লিস্ট দেওয়া আছে। তো আমরা প্রথমে সংখ্যা গুলোকে একটি array ভেরিয়েবলের মধ্যে নিব।

int ara[] = {13, 36, 8, 45, 52, 19, 136, 76};

শুরুতে সংখ্যাটি লিস্টের কততম পজিশনে আছে তা আমাদের জানা নেই। সংখ্যাটি লিস্টের প্রথম পজিশনে থাকতে পারে, মধ্যখানেও থাকতে পারে আবার একেবারে শেষ পজিশনেও থাকতে পারে। যদি লিস্টের শেষ পজিশনে থাকে তাহলে আমাদের এক এক করে মোট আটবার খোঁজা লাগবে। তো আমরা লিস্টের শেষ প্রান্ত ধরে আটবার খোঁজার জন্য n = 8; নামের একটি ভেরিয়েবল নিব। এই ভেরিয়েবলটাকে আমরা লুপের মধ্যে অ্যারের ইলিমেন্ট হিসেবে ব্যবহার করব। এই ব্যপারটা অবশ্যই মনে রাখবে অ্যারে লিস্ট থেকে সংখ্যা খোঁজার জন্য অ্যারের ইলিমেন্ট নম্বর ব্যবহার করব। প্রোগ্রামটি তাহলে লিখে ফেলি- 

আমরা যেহুতু 45 সংখ্যাটি খুঁজতে চাই  সেজন্য 9 নম্বর লাইনে item ভেরিয়েবলে 45 সংখ্যাটি রেখেছি। 13 নম্বর লাইনে ফর লুপের কন্ডিশন বার বার চেক করবে এবং সে অনুযায়ী কাজ করবে। প্রথমবারের ক্ষেত্রে list [i] অর্থাৎ ইলিমেন্ট নাম্বার 0 এর মান 13 কাজেই if কন্ডিশনের শর্ত (13 == 45) সত্য নই। সুতরাং প্রোগ্রামটি if কন্ডিশনের মধ্যে না ঢুকে লুপের আরো এক বাড়বে। এরপর আবার if কন্ডিশনের শর্ত চেক করবে। শর্ত সত্য না হওয়া পর্যন্ত লুপের মান এক এক করে বাড়তে থাকবে। এভাবে যখন if কন্ডিশনের শর্ত (list [i] == item) সত্য হবে তখন প্রোগ্রামটি if ব্লকের মধ্যে ঢুকবে। সার্চকৃত সংখ্যাটি পাওয়া গেলে তা প্রিন্ট করে লুপ break করবে। break ব্যবহারের সুবিধা হল সংখ্যাটি যদি অ্যারের প্রথম ইলিমেন্ট থাকে তাহলে লুপ মাত্র একবার ঘুরে প্রোগ্রামটি শেষ হয়ে যাবে। এতে প্রোগ্রামের সময় কম লাগবে।
লুপের মধ্যের if কন্ডিশনের শর্ত সত্য না হলে অবশ্যয়ই 23 নম্বর লাইনের if কন্ডিশনের শর্ত সত্য হবে। তোমরা নিশ্চয় লক্ষ্য করেছো আমি শুরুতে j ভেরিয়েবল ডিক্লেয়ার করে তার মান 0 দিয়েছি। 18 নম্বর লাইনে j++ লেখা আছে। এর মানে হল list [i] == item শর্তটি সত্য হলে j ভেরিবেলের মান 0 থেকে 1 বাড়বে। list [i] == item শর্তটি সত্য না হলে অর্থাৎ সার্চকৃত সংখ্যাটি লিস্টে না থাকলে  j = 0 থেকে যাবে। তখন প্রিন্ট করবে The number is not found।
সুতরাং উপরের প্রোগ্রামটি রান করালে আউটপুট দেখাবে-
45 is found
This Location is 4 on the list