پیاده سازی جست و جوی دو دویی در جاوا به صورت زیر است :
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 برای ایرانیان مقیم اروپا از وب سایت آمازون
نظر شما در مورد این نوشته چیست؟