زبان برنامه نویسی

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

پیاده سازی جست و جوی دو دویی در جاوا به صورت زیر است :

 

public static int binarySearch(int[] a, int key)

{

     int lo = 0, hi = a.length – 1;

     while (lo <= hi)

{

          int mid = lo + (hi – lo) / 2;

          if          (key < a[mid]) hi = mid – 1;

          else if  (key > a[mid]) lo = mid +1;

          else return mid;

}

      return -1;

}

در پیاده سازی بالا متغیر hi کوتاه شده عبارت High از زبان انگلیسی ، متغیر mid کوتاه شده عبارت Middle و متغیر lo کوتاه شده عبارت Low است.

پیاده سازی جست و جوی دو دویی در جاوا به صورت بازگشتی 

در زبان جاوا (یا هر زبان برنامه نویسی دیگری) ، می توان این الگوریتم را به صورت بازگشتی نیز نوشت. که در آن صورت پیاده سازی به شرح زیر خواهد بود :

public static int binarySearch(int[] a, int key, int lo, int hi )

{

     if (hi < lo) return -1;

     int mid = lo + (hi – lo) / 2;

     if (key < a[mid])

          return binarySearch(a, key, lo, mid – 1);

     else if (key > a [mid])

          return binarySearch(a, key, mid + 1, hi);

else return mid;

}


لینک خرید کتاب Introduction to Java Programming and Data Structures, Comprehensive Version, Global Edition برای ایرانیان مقیم اروپا از وب سایت آمازون

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

زبان برنامه نویسی

اندازه گیری زمان اجرای الگوریتم ها در جاوا

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

به این منظور می توانیم از API آماده StopWatch در جاوا استفاده کنیم. ساختار کلی StopWatch به صورت زیر است :

Public class Stopwatch

                            Stopwatch ()

              double elapsedTime ()

همان طور که در بالا مشاهده می کنید ، این API ساختار بسیار ساده ای دارد. کافی ست که قطعه کد مورد نظر خود را در بین دو المان Stopwatch و double elapsedTime قرار دهید.

برای مثال فرض کنید ، شما قطعه کدی به این صورت در اختیار دارید :

Public static void main (String[] args)

{

              Int [] a = In.readInts (args[0]);

              StdOut.Prinln (BiTJoO.count(a));

}

حال شما قصد دارید ، زمان اجرای StdOut.Println که حاوی یک count هست را بررسی کنید. کافی ست به این صورت عمل کنید :

Public static void main (String[] args)

{

              Int [] a = In.readInts (args[0]);

              Stopwatch timer = new Stopwatch();

              StdOut.Prinln (BiTJoO.count(a));

              Double time = timer.elapsedTime();

}

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