الگوریتم جستجو خطی یا Linear Search در پایتون

درک کردن چگونگی کارکرد الگوریتم‌ها یکی از موضوعات مهمی‌ست که برنامه‌نویسان حرفه‌ای باید اون رو حتما یاد بگیرند. برای همین موضوع شما به عنوان یک برنامه نویس حرفه‌ای پایتون حتما باید با تک تک الگوریتم‌ها و چگونگی پیاده‌سازی‌شون آشنا بشید.

زمانی که ما قصد جستجو کردن یک آیتم در یک لیست را داشته باشیم دقیقا کامپیوتر این کار را به چه صورتی انجام می‌دهد؟ برای انجام چنین کاری الگوریتم‌های جستجوی مختلفی بوجود آمده‌اند که من توی این بلاگ پست می‌خوام شما رو با اولین و ساده‌ترین موردش که جستجوی خطی هستش آشنا بکنم.

جستجو خطی

بگذارید کارکرد این الگوریتم رو در یک مثال براتون توضیح بدم. تصور کنید که شما لیستی شامل اعداد یک تا ده رو دارید و می‌خواید عدد ۶ رو در این لیست پیدا کنید. زمانی که عملیات جستجو رو انجام می‌دید در الگوریتم جستجو خطی از ابتدا یا انتها ایندکس‌ها به صورت تک به تک بررسی می‌شن و در نهایت به ایندکس مربوط به عدد ۶ می‌رسه. پس در این جستجو ایندکس‌ها به صورت تک به تک بررسی می‌شن و در بسیاری از حالت‌ها این الگوریتم بسیار کُند عمل می‌کند.

الگوریتم جستجو خطی

برای پیاده‌سازی این حالت در پایتون ما به یک لیست نیاز داریم (یا هر دیتا استراکچر دیگه‌ای که iterable باشه) و یک مقدار هدف یا چیزی که دنبال‌ش هستیم.

در مرحله بعدی باید تک تک آیتم‌های لیست رو با مقدار هدف‌مون مقایسه بکنیم اگه که برابر بود در نهایت می‌تونیم اندیس اون مقدار رو برگردونیم و اگر نتونستیم مقدار None رو برخواهیم گردوند. به کد نمونه زیر دقت کنید.

def linear_search(list, target):
    '''
    Return list index position if target found, else return None!
    '''
    
    for i in range(0, len(list)):
        if list[i] == target:
            return i
    return None

def varify(index):
    if index is not None:
        print('We found index at: ', index)
    else:
        print('We cant find the index')


numbers = [x for x in range(0,200,2)]

search = linear_search(numbers, 100)

varify(search)

بدون دیدگاه برای الگوریتم جستجو خطی یا Linear Search در پایتون

    دیدگاهتان را بنویسید

    نشانی ایمیل شما منتشر نخواهد شد.

    یک × 4 =