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

  একটা ছবির অ্যালবাম যেখানে আমাদের দেশের সহ অনেক দেশেরই ক্রিকেট প্লেয়ারদের ছবি আছে ।আপনাকে সেই ছবির অ্যালবাম হাতে ধরিয়ে দিয়ে বলা হইলো যে, সাকিব-আল-হাসানের ছবিটা বের করতে । আপনি হয়তো ছবিটা এলোমেলো ভাবে খোজা-খোজি শুরু করে দিবেন যদি ভাগ্য ভালো থাকে তাহলে হয়তো খুব তাড়াতাড়িই পেয়ে যাবেন আবার এমনটাও হতে পারে যে এলোমেলো ভাবে খোজা-খোজির কারণে ছবিটা খুজেই পাচ্ছেন নাহ ।

এখন আপনি যদি অ্যালবামের শুরু থেকে ছবিটা খুজতে থাকেন তাহলে হয়তো প্রথমেই পেতে পারেন অথবা শেষে বা মাঝেও পেতে পারেন । যদি ছবিটি অ্যালবামে থাকে তাহলে এক সময় আপনি তা খুজে পাবেন আর যদি ছবিটা পাওয়া না যায় তাহলে সহজেই বলতে পারেন যে ছবিটা অ্যালবামে নেই বাঁ পাওয়া যায় নাই ।

এই যে,  আপনি অ্যালবামের শুরু থেকে একটির পর একটি ছবিটি খুজতেছেন এই প্রক্রিয়াকেই বলে লিনিয়ার বা সিকোয়েন্সিয়াল সার্চ । যদি বাংলায় বলা হয় তাহলে হবে একাধারে বাঁ একটির পর একটি খোজ করা । এখন যদি আমরা অ্যালবামকে একটি অ্যারে হিসেবে বিবেচনা করি তাহলে প্রত্যেকটা প্লেয়ার হবে অ্যারের এলিমেন্ট বাঁ উপাদান । এবং অ্যারেটা হবে এইরকম -

let players = ["warner","rohit","mustafizur","sakib","bravo","taylor"];

এখন এই অ্যারে থেকে আমি "sakib" কে খুজে বের করতে চাচ্ছি । তাহলে আমাকে অ্যারের প্রথম উপাদান থেকে খোজা শুরু করতে হবে যা লিনিয়ার সার্চের বৈশিষ্ট । দেখতে পাচ্ছি উপরোক্ত অ্যারের প্রথম ইনডেক্সে অর্থাৎ 0 নাম্বার ইনডেক্সে "warner" আছে যা "sakib" নাহ । তাই প্রথম ইনডেক্স হবে নাহ কারণ কন্ডিশন মিথ্যা -


 
অ্যারের পরের উপাদান হচ্ছে "rohit" যা "sakib" নাহ তাহলে এই কন্ডিশনও মিথ্যা -

সেইমভাবে 2 নাম্বার ইনডেক্সের কন্ডিশনও মিথ্যা । এইভাবে একাধারে অর্থাৎ একটার পর একটা খোজ করতেই থাকবে যতক্ষণ নাহ পর্যন্ত কাঙ্ক্ষিত রেজাল্ট পাওয়া যায় । অবশেষে 3 নাম্বার ইনডেক্সের উপাদানই হচ্ছে আমাদের কাঙ্ক্ষিত উপাদান -

 

এখন আমরা লিনিয়ার সার্চ অ্যালগরিদম লিখব এবং তা ইমপ্লিমেন্ট করবো ।

- লিনিয়ার সার্চ অ্যালগরিদম -

একটি অ্যালগরিদম অনেক ভাবেই লিখা যায় তাই অন্য কোথাও অন্য ভাবে দেখে থাকলে চিন্তার কিছু নাই । শুধুমাত্র আমাদের খেয়াল রাখতে হবে যে অ্যালগরিদমটি যেনো সঠিকভাবে কাজ করে । এখন আমরা উপরের অ্যালগরিদমটি জাভাস্ক্রিপ্ট প্রোগ্রামিং ভাষা ব্যাবহার করে ইমপ্লিমেন্ট করি -

const linearSearch = (arr,searchItem) => {
    for(let i = 0; i<arr.length; i++){
        if(arr[i] === searchItem){
            return i;
        }
    }
    return -1;
}

এটাই লিনিয়ার সার্চ অনেক সোজা তাই নাহ ? এখন আমি একটু চেক করি যে আউটপুট ঠিকঠাক দেয় কি নাহ -

let players = ["warner","rohit","mustafizur","sakib","bravo","taylor"];
const res = linearSearch(players, 'sakib');
console.log(res);
// Output : 3

এখন এমন একটি ভ্যালু পাস করি যা উপরোক্ত অ্যারেতে নেই -

let players = ["warner","rohit","mustafizur","sakib","bravo","taylor"];
const res = linearSearch(players, 'shakil');
console.log(res);
// output: -1

যেহেতু, 'shakil' নামে কোনো উপাদান অ্যারেতে নেই তাই আউটপুটে আমরা -1 পেয়েছি যা আমাদের পাওয়ার কথা ছিলো । আশা করি আপনারা লিনিয়ার সার্চ অ্যালগরিদমটি বুঝতে পারছেন ।

 

- লিনিয়ার সার্চের কমপ্লিক্সিটি(Complexity) -

যদি আপনি আমার আগের আর্টিকেলগুলো দেখে থাকেন টাইম এবং স্পেস কমপ্লিক্সিটি(Complexity) নিয়ে তাহলে হয়তো খুব সহজেই বলতে পারবেন লিনিয়ার সার্চের টাইম এবং স্পেস কমপ্লিক্সিটি(Complexity) কত ?

লিনিয়ার সার্চ অ্যালগরিদমের স্পেস কমপ্লিক্সিটি(Complexity) হচ্ছে অর্ডার অব ওয়ান O(1) । কারণ, প্রোগ্রামে একটি মাত্র অ্যারেই আমাদের কে নিতে হবে এবং সেই অ্যারের মাঝেই searchItem টি খুজতে থাকবে । এখানে অ্যারেতে কোনো উপাদান সংযোজন বাঁ বিয়োজন হচ্ছে নাহ, আগের যে উপাদানগুলো আছে তার ভেতরেই searchItem খুজতেছে তাই বলাই যায় অ্যারেটি কন্সট্যান্ট(Constant) ।

লিনিয়ার সার্চ অ্যালগরিদমের টাইম কমপ্লিক্সিটি(Complexity) হচ্ছে অর্ডার অব এন O(n) । যদি কমপ্লিক্সিটি(Complexity) বিষয়টি নাহ বুঝে থাকেন তাহলে নিম্নোক্ত আর্টিকেলগুলো পড়তে পারেন সব ক্লিয়ার হবে যাবে -

১। অ্যালগরিদমে টাইম কমপ্লিক্সিটি(Complexity) - পর্ব(০১) 

২। অ্যালগরিদমে টাইম কমপ্লিক্সিটি(Complexity) - পর্ব(০২)

৩। অ্যালগরিদমে স্পেস কমপ্লিক্সিটি(Complexity) 

# linear search in algorithm

# linear search in javascript

---