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

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

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 به 12؛
4. از آنجایی که عنصر اندیس 12بزرگتر از 55 می‌باشد یک گام به عقب برمی‌گردیم تا به اندیس 9 برسیم.
5. از اندیس 9 جستجوی خطی را آغاز می‌کنیم تا به مقدار 55 برسیم.

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

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

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

     namespace Jump_Search
{
    class MainClass
    {
        public static void Main (string[] args)
        {
            int[] arr = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610 };
            int x = 5;


            int index = jumpSearch(arr, x);


            Console.WriteLine("Number " + x + " is at index " + index);

            Console.ReadKey ();
        }

        public static int jumpSearch(int[] arr, int x) {
            int n = arr.Length;


            int step = (int)  Math.Floor(Math.Sqrt(n));


            int prev = 0;
            while (arr[Math.Min(step, n) - 1] < x) {
                prev = step;
                step += (int) Math.Floor(Math.Sqrt(n));
                if (prev >= n)
                    return -1;
            }


            while (arr[prev] < x) {
                prev++;


                if (prev == Math.Min(step, n))
                    return -1;
            }
                
            if (arr[prev] == x)
                return prev;

            return -1;
        }
    }
}