পাইথনে লিনিয়ার সার্চ প্রোগ্রাম লিখুন

লিনিয়ার সার্চ একটি অ্যারে থেকে কোনো নির্দিষ্ট ভ্যালু খুঁজে বের করার সার্চিং টেকনিক। এটি সবচেয়ে সহজ সার্চিং টেকনিক।

এই সার্চিং টেকনিকেই,

• সার্চ করার ভ্যালুটিকে অ্যারেতে সব এলিমেন্টের সাথে তুলনা করা হয়।
• যদি ভ্যালুটা পাওয়া যায়, তবে সেই এলিমেন্টের ইনডেক্স রিটার্ন করা হয়।
• যদি নির্দিষ্ট এলিমেন্ট পুরো অ্যারেতে না থাকে, তবে -1 বা কোনো প্রাসঙ্গিক স্ট্রিং মেসেজ রিটার্ন করা হয়।

সিউডোকোড

linearSearch(int array[], int value):
    for i=0 to len(array):
        if(array[i]==value):
            Element is Present
    //outside for loop
    Element Not Present // element not found in the whole array

উদাহরণ

def linearSearch(arr, value):
    for i in range(len(arr)):
        if(arr[i] == value):
            return i
    return -1

array = [1,2,3,4,5,6,7,8,9,10]
value = 5
a = linearSearch(array, value)

if(a == -1):
    print("Element not present")
else:
    print("Element present at index", a)

আউটপুট

Element present at index 4

টাইম কমপ্লেক্সিটি

লিনিয়ার সার্চের ওয়ার্স্ট কেস টাইম কমপ্লেক্সিটি O(n)। ওয়ার্স্ট কেস ঘটে যখন এলিমেন্টটি অ্যারেতে শেষ ইনডেক্সে থাকে বা একদম নেই।

লিনিয়ার সার্চের বেস্ট কেস টাইম কমপ্লেক্সিটি O(1)। বেস্ট কেস ঘটে যখন এলিমেন্টটি অ্যারেতে প্রথম ইনডেক্সে থাকে।

উন্নত লিনিয়ার সার্চ

লিনিয়ার সার্চের ওয়ার্স্ট কেস কমপ্লেক্সিটি O(n/2) তে উন্নত করা যায়। এটি টু পয়েন্টার (left এবং right) ব্যবহার করে একই সাথে দুটি তুলনা করে করা যায়, ফলে ওয়ার্স্ট কেস টাইম কমপ্লেক্সিটি O(n/2) হয়ে যায়।

উদাহরণ

def linearSearch(arr, value):
    left = 0
    right = len(arr) - 1
    while(left <= right):
        if(arr[left] == value):
            return left
        elif(arr[right] == value):
            return right
        left += 1
        right -= 1
    return -1

array = [1,2,3,4,5,6,7,8,9,10]
value = 10
a = linearSearch(array, value)

if(a == -1):
    print("Element not present")
else:
    print("Element present at index", a)

আউটপুট

Element present at index 9

উপরোক্ত উদাহরণে, শেষ ইনডেক্সে থাকা এলিমেন্টটি প্রথম ইটারেশনে পাওয়া যায়। প্রথম মেথডে এটি খুঁজে পেতে ১০ ইটারেশন লাগত।

যদি এলিমেন্টটি না পাওয়া যায়, তবে ওয়ার্স্ট কেস কমপ্লেক্সিটি O(n/2), কারণ দ্বিতীয় মেথডে মোট ইটারেশন n/2 হয়।

লিনিয়ার সার্চ কতটুকু কার্যকর?

লিনিয়ার সার্চ খুব কম ব্যবহৃত হয় কারণ বাইনারি সার্চের মতো আরও ভালো সার্চিং অ্যালগরিদম আছে যা ভালো টাইম কমপ্লেক্সিটি দেয়। বড় ইনপুট অ্যারেতে লিনিয়ার সার্চ কার্যকর নয়।