paython13






آموزش جستجوی خطی و دودویی در پایتون | ۱۰ پروژه جذاب برای نوجوانان


🔍 جستجوی خطی (Linear) و جستجوی دودویی (Binary) در پایتون

📌 جستجوی خطی (Linear Search)

✅ ساده‌ترین روش جستجو: تک تک عناصر آرایه را از اول تا آخر چک می‌کنیم تا مقدار مورد نظر را پیدا کنیم.
➕ مزایا: نیازی به مرتب بودن داده ندارد، برای هر لیستی کار می‌کند.
➖ معایب: اگر آرایه بزرگ باشد، کند است (بیشترین زمان در بدترین حالت).
💡 مانند گشتن برگه‌های یک کتاب به ترتیب صفحه به صفحه.

مثال: for i in range(len(arr)): if arr[i]==target: found

⚡ جستجوی دودویی (Binary Search)

✅ بسیار سریع! آرایه باید حتماً مرتب شده باشد. هر بار لیست را نصف می‌کنیم و مقدار میانی را مقایسه می‌کنیم.
➕ مزایا: برای داده‌های بزرگ خیلی سریع (log n) است.
➖ معایب: فقط برای لیست‌های مرتب شده کار می‌کند.
💡類似 جستجوی کلمه در فرهنگ لغت: نیم‌نگاه می‌کنی و محدوده را کوچک می‌کنی.

while low <= high: mid = (low+high)//2 and compare

پروژه ۱: پیدا کردن عدد مخفی (جستجوی خطی ساده)

📖 سوال پروژه

یک لیست از اعداد ۱ تا ۲۰ بسازید. کاربر یک عدد وارد می‌کند، برنامه با جستجوی خطی بگوید که آیا عدد در لیست هست یا خیر و ایندکس آن را نمایش دهد.

🖥️ خروجی نمونه

لیست: [۱,۲,۳,…,۲۰]
عدد مورد نظر: ۱۵
✅ پیدا شد در اندیس ۱۴
عدد: ۲۵ ❌ پیدا نشد

🐍 حل پروژه

# جستجوی خطی - پروژه ۱
numbers = list(range(1, 21))  # 1 تا ۲۰
target = int(input("یک عدد بین ۱ تا ۲۰ وارد کن: "))

found_index = -1
for i in range(len(numbers)):
    if numbers[i] == target:
        found_index = i
        break

if found_index != -1:
    print(f"✅ عدد {target} در اندیس {found_index} پیدا شد.")
else:
    print("❌ عدد در لیست وجود ندارد.")

پروژه ۲: فرهنگ اعداد (جستجوی دودویی)

📖 سوال پروژه

یک آرایه مرتب از ۵۰ عدد تصادفی (مرتب شده) بسازید. از کاربر عددی بگیرید و با الگوریتم جستجوی دودویی پیدا کنید و تعداد گام‌های جستجو را نمایش دهید.

🖥️ خروجی نمونه

آرایه مرتب: [۲,۵,۷,۱۲,۱۹,۲۲,…]
عدد: ۱۲ -> پیدا شد در اندیس ۳، تعداد گام: ۲

🐍 حل پروژه

import random
arr = sorted(random.sample(range(10,200), 50))
print("آرایه مرتب:", arr[:10], "...")
target = int(input("عدد مورد نظر: "))

low, high = 0, len(arr)-1
steps = 0
found = False
while low <= high:
    steps += 1
    mid = (low + high) // 2
    if arr[mid] == target:
        print(f"🔍 پیدا شد در اندیس {mid} بعد از {steps} گام")
        found = True
        break
    elif arr[mid] < target:
        low = mid + 1
    else:
        high = mid - 1
if not found:
    print(f"❌ پیدا نشد. {steps} گام جستجو.")

پروژه ۳: غیاب و حضور (جستجوی خطی اسم)

📖 سوال پروژه

لیستی از ۱۰ نام دانش آموز داریم. کاربر یک نام وارد کند، با جستجوی خطی بگوید در کدام ردیف (ایندکس) قرار دارد، یا اخطار غایب.

🖥️ خروجی نمونه

لیست: ["سارا","امیر","زهرا","محمد","نازنین"]
نام: زهرا -> زهرا در اندیس ۲ حضور دارد.

🐍 حل پروژه

students = ["سارا", "امیر", "زهرا", "محمد", "نازنین", "علیرضا", "فاطمه", "حسین", "نگار", "کیان"]
name = input("نام دانش آموز: ")

pos = -1
for idx, student in enumerate(students):
    if student == name:
        pos = idx
        break
if pos != -1:
    print(f"✅ {name} در اندیس {pos} کلاس حضور دارد.")
else:
    print(f"❌ {name} در لیست کلاس نیست.")

پروژه ۴: امتیاز قهرمانی (دودویی)

📖 سوال پروژه

لیست مرتبی از امتیازات بازیکنان (۲۰ نمره) داریم. کاربر یک امتیاز بدهد، جستجوی دودویی انجام دهد و بگوید چندمین بازیکن این امتیاز را دارد (بر اساس رتبه).

🖥️ خروجی نمونه

امتیازات: [۱۲۰۰,۱۳۵۰,۱۵۰۰,۱۷۸۰,۲۰۰۰,...]
امتیاز: ۱۵۰۰ -> رتبه ۲ (اندیس ۲)

🐍 حل پروژه

scores = [1100, 1250, 1370, 1490, 1550, 1680, 1720, 1890, 2000, 2150, 2300, 2450]
target = int(input("امتیاز مورد نظر: "))
low, high = 0, len(scores)-1
index = -1
while low <= high:
    mid = (low+high)//2
    if scores[mid] == target:
        index = mid
        break
    elif scores[mid] < target:
        low = mid+1
    else:
        high = mid-1
if index != -1:
    print(f"🏆 این امتیاز در رتبه {index+1} (اندیس {index}) قرار دارد.")
else:
    print("امتیاز یافت نشد")

پروژه ۵: تکرار کلمات (خطی و شمارش)

📖 سوال پروژه

یک لیست از کلمات (مثل میوه‌ها) که ممکن است تکراری باشند، کاربر یک کلمه بدهد، برنامه با جستجوی خطی تعداد دفعات تکرارش را بشمارد.

🖥️ خروجی نمونه

["سیب","موز","سیب","پرتقال","سیب"]
کلمه: سیب -> تعداد تکرار: ۳

🐍 حل پروژه

fruits = ["سیب","موز","سیب","پرتقال","انگور","سیب","کیوی","موز","سیب"]
word = input("کلمه مورد نظر: ")
count = 0
for item in fruits:
    if item == word:
        count += 1
print(f"🔁 کلمه '{word}' {count} بار تکرار شده است.")

پروژه ۶: الفبای رمز (جستجوی دودویی کاراکتر)

📖 سوال پروژه

لیست مرتبی از حروف انگلیسی (a-z) بسازید. کاربر یک حرف وارد کند، با جستجوی دودویی پیدا کنید و بگویید اندیس آن چند است.

🖥️ خروجی نمونه

['a','b','c',...,'z']
حرف: m -> اندیس ۱۲

🐍 حل پروژه

import string
letters = list(string.ascii_lowercase)  # لیست حروف a-z
ch = input("یک حرف انگلیسی کوچک وارد کن: ").lower()
low, high = 0, len(letters)-1
res = -1
while low <= high:
    mid = (low+high)//2
    if letters[mid] == ch:
        res = mid
        break
    elif letters[mid] < ch:
        low = mid+1
    else:
        high = mid-1
if res != -1:
    print(f"حرف '{ch}' در اندیس {res} قرار دارد.")
else:
    print("پیدا نشد")

پروژه ۷: مسابقه سرعت! خطی در برابر دودویی

📖 سوال پروژه

یک لیست مرتب ۱۰۰۰۰ تایی بسازید. یک مقدار را هم با خطی و هم با دودویی جستجو کنید و زمان اجرای هر دو را مقایسه کنید.

🖥️ خروجی نمونه

زمان جستجوی خطی: ۰٫۰۰۲۳ ثانیه
زمان جستجوی دودویی: ۰٫۰۰۰۰۱۲ ثانیه
دودویی خیلی سریع‌تر!

🐍 حل پروژه

import time
big_list = list(range(100000))  # 0 تا ۹۹۹۹۹
target = 98765

# خطی
start = time.time()
found_lin = target in big_list  # داخلی اما مشابه خطی
end = time.time()
print(f"جستجوی خطی: {(end-start)*1000:.5f} میلی‌ثانیه")

# دودویی
start = time.time()
low, high = 0, len(big_list)-1
found_bin = False
while low <= high:
    mid = (low+high)//2
    if big_list[mid] == target:
        found_bin = True
        break
    elif big_list[mid] < target:
        low = mid+1
    else:
        high = mid-1
end = time.time()
print(f"جستجوی دودویی: {(end-start)*1000:.5f} میلی‌ثانیه")

پروژه ۸: جعبه فیلم (جستجوی خطی عناوین)

📖 سوال پروژه

لیستی از ۸ عنوان فیلم محبوب نوجوانان داریم. کاربر عنوانی بدهد، برنامه جستجوی خطی انجام داده و بگوید در چه جایگاهی (شماره ۱ تا ۸) قرار دارد.

🖥️ خروجی نمونه

["هری پاتر","ارباب حلقه ها","ونوم","تایتانیک"]
فیلم: ونوم -> رتبه ۳

🐍 حل پروژه

movies = ["هری پاتر", "ارباب حلقه ها", "ونوم", "تایتانیک", "اینترنت پدر", "رئونیون", "تام و جری", "سونیک"]
search = input("نام فیلم: ")
found = False
for i, movie in enumerate(movies):
    if movie == search:
        print(f"🎬 فیلم «{search}» در جایگاه {i+1} (اندیس {i}) قرار دارد.")
        found = True
        break
if not found:
    print("فیلم در فهرست نیست")

پروژه ۹: حراجی سرعت (دودویی قیمت)

📖 سوال پروژه

لیست مرتبی از قیمت کالاها (۱۰ عدد). کاربر یک محدوده قیمت (حداقل و حداکثر) بدهد، با جستجوی دودویی اولین و آخرین اندیس کالاهای آن بازه را پیدا کنید (محدوده).

🖥️ خروجی نمونه

قیمت‌ها: [۱۵۰۰۰,۲۳۰۰۰,۳۵۰۰۰,۴۷۰۰۰,۵۲۰۰۰,۶۸۰۰۰]
بازه ۲۰۰۰۰ تا ۵۰۰۰۰ -> اندیس‌های ۱ تا ۴

🐍 حل پروژه

prices = [12000, 18900, 24500, 33700, 42800, 51400, 63000, 75900]
low_price = int(input("حداقل قیمت: "))
high_price = int(input("حداکثر قیمت: "))

def first_index(arr, val):
    low, high = 0, len(arr)-1
    ans = -1
    while low <= high:
        mid = (low+high)//2
        if arr[mid] >= val:
            ans = mid
            high = mid-1
        else:
            low = mid+1
    return ans

def last_index(arr, val):
    low, high = 0, len(arr)-1
    ans = -1
    while low <= high:
        mid = (low+high)//2
        if arr[mid] <= val:
            ans = mid
            low = mid+1
        else:
            high = mid-1
    return ans

left = first_index(prices, low_price)
right = last_index(prices, high_price)
if left != -1 and right != -1 and left <= right:
    print(f"💰 کالاهای با قیمت بین {low_price} تا {high_price} : اندیس‌های {left} تا {right}")
else:
    print("هیچ کالایی در این بازه نیست")

پروژه ۱۰: پیدا کردن یار همیشگی (خطی و دودویی روی لیست دوستان)

📖 سوال پروژه

لیست دوستان (اسامی) را مرتب کرده و هم با جستجوی خطی و هم دودویی یک اسم خاص را جستجو کن. در نهایت بگو هر دو روش جواب یکسان می‌دهند.

🖥️ خروجی نمونه

دوستان: ['احسان','سارا','مریم','نوید'] مرتب: ['احسان','مریم','نوید','سارا']
نام: سارا -> خطی اندیس ۳, دودویی اندیس ۳

🐍 حل پروژه

friends = ["سارا", "احسان", "مریم", "نوید", "لیلا"]
friends_sorted = sorted(friends)
print("لیست مرتب شده:", friends_sorted)
target = input("اسم دوست خود را بگو: ")

# جستجوی خطی روی لیست اصلی (غیرمرتب)
linear_idx = -1
for i, name in enumerate(friends):
    if name == target:
        linear_idx = i
        break

# جستجوی دودویی روی لیست مرتب
low, high = 0, len(friends_sorted)-1
binary_idx = -1
while low <= high:
    mid = (low+high)//2
    if friends_sorted[mid] == target:
        binary_idx = mid
        break
    elif friends_sorted[mid] < target:
        low = mid+1
    else:
        high = mid-1

if linear_idx != -1:
    print(f"جستجوی خطی: {target} در اندیس {linear_idx} لیست اصلی")
    print(f"جستجوی دودویی (مرتب): در اندیس {binary_idx} از لیست مرتب")
else:
    print("دوست مورد نظر یافت نشد")
🚀 حالا شما هم می‌توانید هر لیستی را با خطی (ساده اما کند برای داده بزرگ) یا دودویی (فوق سریع ولی نیاز به مرتب بودن) جستجو کنید! هر ۱۰ پروژه را در پایتون اجرا کنید و مهارت خود را محک بزنید.


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

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *