جستجوی پرشی در جاوا (Jump Search in Java)

در این قسمت تیم کدگیت را با آموزش جستجوی پرشی در جاوا همراهی کنید. در ابتدا طبق روال آموزش‌های گذشته، توضیح کوتاهی در مورد جستجوی پرشی خواهیم داد و سپس با ذکر مثالی ساده الگوریتم جستجوی پرشی در جاوا را پیاده‌سازی خواهیم کرد. همچنین پیشنهاد می‌کنیم قبل از مطالعه این جلسه، آموزش‌های زیر را مطالعه کنید:

  1. آشنایی با متد Static در جاوا
  2. آشنایی با while در جاوا
  3. آشنایی با آرایه در جاوا

جستجوی پرشی

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

فرض کنید که یک آرایه [] به اندازه n وبلوکی( که ازش میپریم) به اندازه m داریم. حالا در فهرست های [0],[m],[2m],…[km] و … به جستجو می‌پردازیم. به محض اینکه فاصله ( [km] < x < [(k+1)m] ) را پیدا کردیم، عملیات جستجوی خطی را در فهرست   km  تا هنگامی که  عنصر x  را پیدا کنیم ادامه می‌دهیم.

آرایه زیر را در نظر داشته باشید:

( 0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 , 89 , 144 , 233 , 377 , 610 ).

طول این آرایه 16 می‌باشد. جستجوی پرشی مقدار 55 را از طریق گام های زیر با فرض اینکه اندازه هر بلوک 4 است پیدا می‌کند.

  1. پرش از اندیس0 به 4؛
  2. پرش از اندیس 4 به 8؛
  3. پرش از اندیس 8 به 16؛
  4. از آنجایی که عنصر اندیس 16 بزرگتر از 55 می‌باشد یک گام به عقب برمی‌گردیم تا به اندیس 9 برسیم.
  5. از اندیس 9 جستجوی خطی را آغاز می‌کنیم تا به مقدار 55 برسیم.

حال سوال اینجاست مناسب ترین اندازه ای که یک بلوک جهت پرش می‌تواند داشته باشد چقدر است؟ از طریق ریاضی بهترین سایز بلوک n√ می‌باشد که در این آموزش به اثبات آن نمی‌پردازیم.

پیاده‌سازی جستجوی پرشی در جاوا

برای پیاده‌سازی جستجوی پرشی در جاوا یک متد به نام JumpSearch می‌نویسیم. با تعیین بلاک آرایه (متغیر Step در کد) به جستجوی [0],[m],[2m],…[km] که در قسمت قبل توضیح دادیم، می‌پردازیم (While اول در کد). در While دوم جستجوی خطی را انجام می‌دهیم و در آخر اندیس خانه مورد جستجو را بر‌می‌گردانیم. کد این الگوریتم به صورت زیر می‌باشد:

   پسورد: www.codegate.ir

دسته : java, جاوا, ساختمان داده در جاوا

دیدگاه بگذارید

نظر شما چیست؟

مطلع کردن شما از
avatar

wpDiscuz