الگوریتم های جستجو یا Search Algorithms

توی این پست بهتون ی دید کلی از الگوریتم های جستجو همراه با نمونه کد میگم :)

خب باید بدونیم که Search Algorithms ستون فقرات بازیابی داده ها و پیمایش در ساختار های داده ای مختلف (مثل آرایه‌ها، درخت‌ها و گراف‌ها) هستن.

الگوریتم‌های جستجو ابزارهایی هستن که برای پیدا کردن عنصر مورد نظر ما در یک ساختار داده (مثل آرایه یا لیست) استفاده میشن. انواع مختلفی از این الگوریتم‌ها وجود دارن که هر کدومشون ویژگی‌ها، مزایا و معایب خودشون رو دارن.

در ادامه به معرفی چند الگوریتم جستجوی رایج، همراه با توضیح مختصر، ویژگی‌ها و نمونه کد به زبان پایتون و جاوااسکریپت می‌پردازیم

به این پایینیا میپردازیم :)

1. جستجوی خطی (Linear Search)

2. جستجوی دودویی (Binary Search)

3. جستجوی درون‌یابی (Interpolation Search)

4. جستجوی پرشی (Jump Search)

دوسدارم اضافه کنم که اگر زمان اجرا رو متوجه نمیشید ایرادی نداره، برای کسایی که نمیخوان تخصصی مطالعه کنن واقعا ضروری نیست :)

1. جستجوی خطی (Linear Search)➖

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

ویژگی‌ها:

• سادگی: پیاده‌سازی این الگوریتم خیلی راحته.

• کارایی: برای ساختارهای داده کوچیک یا نامرتب (unsorted) کاملا مناسبه.

• زمان اجرا: بدترین حالت زمان اجراش O(n) هست، که توی اون n تعداد عناصر هستش.

python

def linear_search(data, target):
    for i in range(len(data)):
        if data[i] == target:
            return i  # Index of the target element
    return -1  # Target element not found

# Example usage:
my_list = [5, 2, 8, 12, 3, 9]
target_element = 12
index = linear_search(my_list, target_element)
if index != -1:
    print(f"Element {target_element} found at index {index}")
else:
    print(f"Element {target_element} not found")

javascript

function linearSearch(data, target) {
  for (let i = 0; i < data.length; i++) {
    if (data[i] === target) {
      return i; // Index of the target element
    }
  }
  return -1; // Target element not found
}

// Example usage:
const myList = [5, 2, 8, 12, 3, 9];
const targetElement = 12;
const index = linearSearch(myList, targetElement);
if (index !== -1) {
  console.log(`Element ${targetElement} found at index ${index}`);
} else {
  console.log(`Element ${targetElement} not found`);
}

2. جستجوی دودویی (Binary Search)2️⃣2️⃣

اول باید به این نکته توجه کنیم که فقط زمانی میتونیم از الگوریتم دودویی استفاده کنیم که ساختار دادمون مرتب یا sorted باشه.

جستجوی دودویی چطور کار میکنه؟

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

ویژگی‌ها:

• کارایی بالا: برای ساختارهای داده مرتب بسیار سریع هستش.

• زمان اجرا: زمان اجرای آن O(log n) است که بسیار بهتر از جستجوی خطی برای داده‌های بزرگ هست.

• پیش‌نیاز: ساختار داده باید مرتب باشه.

python

def binary_search(data, target):
    low = 0
    high = len(data) - 1
    while low <= high:
        mid = (low + high) // 2
        if data[mid] == target:
            return mid  # Index of the target element
        elif data[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1  # Target element not found

# Example usage:
sorted_list = [2, 3, 5, 8, 9, 12]
target_element = 8
index = binary_search(sorted_list, target_element)
if index != -1:
    print(f"Element {target_element} found at index {index}")
else:
    print(f"Element {target_element} not found")

javascript

function binarySearch(data, target) {
  let low = 0;
  let high = data.length - 1;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (data[mid] === target) {
      return mid; // Index of the target element
    } else if (data[mid] < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return -1; // Target element not found
}

// Example usage:
const sortedList = [2, 3, 5, 8, 9, 12];
const targetElement = 8;
const index = binarySearch(sortedList, targetElement);
if (index !== -1) {
  console.log(`Element ${targetElement} found at index ${index}`);
} else {
  console.log(`Element ${targetElement} not found`);
}

3. جستجوی درون‌یابی (Interpolation Search)

برای استفاده از این الگوریتم باید ساختار داده هامون طور یکنواخت توزیع شده باشن.

جستجوی درون‌یابی چطور کار میکنه؟

این الگوریتم شبیه به جستجوی دودویی هستش، اما با این تفاوت که به جای انتخاب نقطه میانی، موقعیت عنصر احتمالی را بر اساس توزیع داده‌ها تخمین می‌زند. اگر داده‌ها به طور یکنواخت توزیع شده باشند، این الگوریتم سریع‌تر از جستجوی دودویی عمل می‌کند.

توی توزیع یکنواخت، داده‌ها با فواصل قابل پیش‌بینی (مثل ۵ تا ۵ تا، یا ۱۰ تا ۱۰ تا) کنار هم قرار گرفته‌اند.

ویژگی‌ها:

• کارایی: برای داده‌های مرتب و با توزیع یکنواخت، خیلی سریع‌تر از جستجوی دودویی هستش.

• زمان اجرا: میانگین زمان اجرا O(log log n) هست، اما در بدترین حالت میتونه O(n) باشد.

• پیش‌نیاز: ساختار داده باید مرتب و با توزیع نسبتاً یکنواخت باشد.

python

def interpolation_search(data, target):
    low = 0
    high = len(data) - 1
    while low <= high and target >= data[low] and target <= data[high]:
        if low == high:
            if data[low] == target:
                return low
            return -1

        # Estimate position
        pos = low + int(((float(high - low) / (data[high] - data[low])) * (target - data[low])))

        if data[pos] == target:
            return pos
        elif data[pos] < target:
            low = pos + 1
        else:
            high = pos - 1
    return -1

# Example usage:
sorted_uniform_list = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
target_element = 70
index = interpolation_search(sorted_uniform_list, target_element)
if index != -1:
    print(f"Element {target_element} found at index {index}")
else:
    print(f"Element {target_element} not found")

javascript

function interpolationSearch(data, target) {
  let low = 0;
  let high = data.length - 1;
  while (low <= high && target >= data[low] && target <= data[high]) {
    if (low === high) {
      if (data[low] === target) return low;
      return -1;
    }

    // Estimate position
    const pos = low + Math.floor(((high - low) / (data[high] - data[low])) * (target - data[low]));

    if (data[pos] === target) {
      return pos;
    } else if (data[pos] < target) {
      low = pos + 1;
    } else {
      high = pos - 1;
    }
  }
  return -1; // Target element not found
}

// Example usage:
const sortedUniformList = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100];
const targetElement = 70;
const index = interpolationSearch(sortedUniformList, targetElement);
if (index !== -1) {
  console.log(`Element ${targetElement} found at index ${index}`);
} else {
  console.log(`Element ${targetElement} not found`);
}

4. جستجوی پرشی (Jump Search)

مفهوم: این الگوریتم برای لیست‌های مرتب استفاده می‌شود. ایده اصلی این است که به جای بررسی هر عنصر، عناصر را با گام‌های مشخصی (مثلاً هر √n عنصر) بررسی کنیم. اگر عنصری که به دنبال آن هستیم از گام فعلی بزرگتر بود، به گام بعدی می‌پرویم. اگر از گام فعلی کوچکتر بود، آنگاه در بازه بین گام قبلی و فعلی، جستجوی خطی انجام می‌دهیم.

اگه بخوام ی سناریو ساده بگم برای درکش فرض کن دنبال شماره پلاک ۷۵ در یک خیابان هستی که پلاک خانه‌های اون از ۱ تا ۱۰۰ به ترتیب شماره گذاری شدن، اما تو نمی‌خوای جلوی تک‌تک خونه ها توقف کنی (چون خیلی زمان‌بره)

روش کار:

1. پرش‌های بزرگ: تصمیم می‌گیری هر ۱۰ خونه یک‌بار توقف کنی و شماره پلاک رو نگاه کنی. (یعنی پلاک ۱۰، ۲۰، ۳۰، …).

2. پیدا کردن محدوده: همین‌طور که داری می‌پری، به پلاک ۷۰ می‌رسی و خانه بعدی پلاک ۸۰ است.

3. توقف: چون ۷۵ بین ۷۰ و ۸۰ است، می‌فهمی که خونه مورد نظرت توی همین بلوک ۱۰ خونه‌ای (بین ۷۰ تا ۸۰) مخفی شده.

4. جستجوی نهایی: حالا فقط همین ۱۰ خونه رو با دقت و به صورت تک‌تک (خطی) چک می‌کنی تا پلاک ۷۵ رو پیدا کنی.

ویژگی‌ها:

• کارایی: سریع‌تر از جستجوی خطی و کندتر از جستجوی دودویی در حالت کلی هستش.

• زمان اجرا: زمان اجراش O(√n) است.

• پیش‌نیاز: ساختار داده باید مرتب باشه.

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

python

import math

def jump_search(data, target):
    n = len(data)
    step = int(math.sqrt(n))
    prev = 0

    # Finding the block where element is present
    while data[min(step, n) - 1] < target:
        prev = step
        step += int(math.sqrt(n))
        if prev >= n:
            return -1

    # Doing a linear search for target in block beginning with prev.
    while data[prev] < target:
        prev += 1
        # If we reached next block or end of array, element is not present.
        if prev == min(step, n):
            return -1

    # If element is found
    if data[prev] == target:
        return prev
    return -1

# Example usage:
sorted_list_jump = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]
target_element = 55
index = jump_search(sorted_list_jump, target_element)
if index != -1:
    print(f"Element {target_element} found at index {index}")
else:
    print(f"Element {target_element} not found")

javascript

function jumpSearch(data, target) {
  const n = data.length;
  let step = Math.floor(Math.sqrt(n));
  let prev = 0;

  // Finding the block where element is present
  while (data[Math.min(step, n) - 1] < target) {
    prev = step;
    step += Math.floor(Math.sqrt(n));
    if (prev >= n) {
      return -1;
    }
  }

  // Doing a linear search for target in block beginning with prev.
  while (data[prev] < target) {
    prev += 1;
    // If we reached next block or end of array, element is not present.
    if (prev === Math.min(step, n)) {
      return -1;
    }
  }

  // If element is found
  if (data[prev] === target) {
    return prev;
  }
  return -1; // Target element not found
}

// Example usage:
const sortedListJump = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610];
const targetElement = 55;
const index = jumpSearch(sortedListJump, targetElement);
if (index !== -1) {
  console.log(`Element ${targetElement} found at index ${index}`);
} else {
  console.log(`Element ${targetElement} not found`);
}

میدونم یکم وقفه افتاد اما تلاشم رو میکنم هرزمان تایمم آزاده براتون سری مقاله های الگوریتم هارو تکمیل کنم :)

اگه دوسدارین مثل گذینه ی اخر برای یادگیری بهترتون سناریو بنویسم برای درک بهتر برام کامنت بزارید و بگید، چون نمیدونم برای هر الگوریتم چقدر حوصله دارین بخونید، من تا حد امکان کوتاه مینویسم و ساده( البته فعلا☺️🙂 )

خوشحال میشم فیدبک هاتون رو برام بنویسید💕