فرادرسبرنامه پیدا کردن k نزدیک ترین عنصر به یک مقدار – راهنمای کاربردی
در این مطلب، روش نوشتن برنامه پیدا کردن k نزدیک ترین عنصر به یک مقدار خاص داده شده در ورودی، آموزش داده شده است. یک آرایه مرتب شده arr[] و مقدار X موجود است. هدف پیدا کردن k عنصر نزدیک به مقدار X در آرایه arr[] است. مثال‌های زیر در این رابطه قابل توجه هستند. شایان ذکر است، پیاده‌سازی روش آموزش داده شده در این مطلب، در زبان‌های برنامهنویسی گوناگون شامل «سی‌پلاس‌پلاس» (++C)، «سی» (C)، «جاوا» (Java)، «پایتون ۳» (Python 3) و «پی‌اچ‌پی» (PHP) انجام شده است.
Input: K = 4, X = 35
arr[] = {12, 16, 22, 30, 35, 39, 42,
45, 48, 50, 53, 55, 56}
Output: 30 39 42 45
شایان توجه است که اگر خود عنصر X در آرایه وجود داشته باشد، نباید در خروجی ارائه شود. در واقع، تنها نزدیک‌ترین عناصر به X هستند که باید در خروجی بازگردانده شوند. در راهکارهای زیر، فرض می‌شود همه عناصر اولیه از یکدیگر متمایز هستند. یک راهکار ساده، انجام جستجوی خطی برای k نزدیک‌ترین عنصر است.
جستجوی خطی برای پیدا کردن k نزدیک ترین عنصر به یک مقدار
- کار را از اولین عنصر آغاز کن و جستجو را برای «نقطه هم‌گذری» (Crossover Point) (نقطه‌ای پیش از X که عناصر کوچک‌تر یا مساوی X باشند و همچنین، نقطه‌ای پس از X که در آن عناصر بزرگ‌تر از X هستند) انجام بده. این گام از مرتبه O(n) است.
- هنگامی که نقطه هم‌گذری پیدا شد، می‌توان عناصر را در دو سمت نقطه هم‌گذری برای چاپ کردن k نزدیک‌ترین عنصر مقایسه کرد. این گام از درجه O(k) است.
جستجوی دودویی برای پیدا کردن k نزدیک ترین عنصر به یک مقدار
پیچیدگی زمانی راهکار بالا (جستجوی خطی) از درجه O(n) است. یک راهکار بهینه، پیدا کردن k عنصر در زمان O(Logn + k) است. برای رسیدن به زمان بیان شده، یک ایده استفاده از «جستجوی دودویی» (Binary Search) برای پیدا کردن نقطه هم‌گذری است. هنگامی که اندیس نقطه هم‌گذری پیدا شد، می‌توان k نزدیک‌ترین عنصر را در زمان O(k) پیدا کرد.
پیدا کردن k نزدیک ترین عنصر به یک مقدار در C/C++ با جستجوی دودویی
پیدا کردن k نزدیک ترین عنصر به یک مقدار در جاوا با جستجوی دودویی
پیدا کردن k نزدیک ترین عنصر به یک مقدار در پایتون ۳ با جستجوی دودویی
پیدا کردن k نزدیک ترین عنصر به یک مقدار در C# با جستجوی دودویی
پیدا کردن k نزدیک ترین عنصر به یک مقدار در PHP با جستجوی دودویی
خروجی قطعه کدهای بالا به صورت زیر است.
39 30 42 45
پیچیدگی زمانی این روش از درجه O(Logn + k) است.
اگر نوشته بالا برای شما مفید بوده است، آموزشهای زیر نیز به شما پیشنهاد می‌شوند:
- مجموعه آموزشهای برنامهنویسی
- آموزش برنامهنویسی C++
- مجموعه آموزشهای ریاضیات
- یافتن دور همیلتونی با الگوریتم پس گرد — به زبان ساده
- الگوریتم بازی مار و پله همراه با کد — به زبان ساده
- حل مساله n وزیر با الگوریتم پس‌گرد (Backtracking) — به زبان ساده
- الگوریتم جست و جوی دودویی در جاوا اسکریپت — به زبان ساده
^^
