جستجوی باینری: یکی از سریعترین الگوریتم جستجو

با توجه به یک آرایه مرتب شده X [] از عناصر n ، یک کلید عنصر معین را در x [] جستجو کنید. اگر کلید وجود دارد ، سپس شاخص خود را در آرایه مرتب شده برگردانید. در غیر این صورت ، بازگش ت-1.

• تمام اعداد صحیح در x [] بی نظیر هستند.
• x [] به ترتیب صعودی طبقه بندی می شود.

مثال 1

ورودی: x [] = [-4 ، 2 ، 4 ، 5 ، 9 ، 12] ، کلید = 5 ، خروجی: 3

توضیح: 5 در x [] در فهرست 3 وجود دارد. بنابراین ما 3 برمی گردیم.

مثال 2

ورودی: x [] = [-4 ، 2 ، 4 ، 5 ، 9 ، 12] ، کلید = 6 ، خروجی: -1

توضیح: 6 در x [] وجود ندارد. بنابراین م ا-1 برمی گردیم.

جستجوی باینری چگونه کار می کند؟

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

حدس خطی تمام مقادیر مداوم 1 ، 2 ،. وادواد16 ناکارآمد خواهد بود زیرا با هر سوال ، ما فقط یک شماره را از بین می بریم. در بدترین حالت ، باید 16 بار حدس بزنیم! آیا می توانیم فکر کنیم که راه حل بهتری پیدا کنیم و شماره را با حداقل تعداد حدس در بدترین حالت پیدا کنیم؟آیا می توانیم از ورودی سفارش مرتب شده استفاده کنیم؟یک بینش ساده است: اگر هر عدد X را در دنباله مرتب شده انتخاب کنیم ، تمام اعداد در سمت چپ کمتر از X خواهند بود و تمام اعداد در سمت راست از X بیشتر خواهند بود.

حال سوال مهم این است: بهترین حدس در ابتدا چه خواهد بود؟ایده ساده است: اعداد به ترتیب مرتب شده ارائه می شوند ، بنابراین بهترین حدس اول انتخاب شماره میانی (8 در اینجا) و کاهش مجموعه اعداد به نصف در یک حرکت است.

• اگر تعداد واقعی برابر با شماره حدس زده (8) باشد ، ما انجام می شود.
• اگر تعداد واقعی کمتر از شماره حدس زده (8) باشد ، در حدس بعدی ما دامنه اعداد را از 9 تا 16 نادیده می گیریم. ما همان فرآیند را برای اعداد 1 تا 8 تکرار می کنیم و شماره میانی 4 و غیره را انتخاب می کنیم.
• اگر تعداد واقعی از شماره حدس زده (8) بیشتر باشد ، در حدس بعدی ما دامنه اعداد را از 1 تا 7 نادیده می گیریم. ما همان فرآیند را برای اعداد 9 تا 16 تکرار می کنیم و شماره میانی 12 و غیره را انتخاب می کنیم.

بعد از هر حدس ، نیمی از شماره های داده شده را به یکباره رد می کنیم. این یک پیشرفت چشمگیر است! ما مجموعه اعداد را با ضریب 1/2 کاهش می دهیم ، بنابراین حداقل تعداد حدس های مورد نیاز در بدترین حالت 4 است. فکر!

الگوریتم جستجوی باینری را تقسیم و تسخیر کنید

ما شروع به جستجوی کلید هدف در آرایه مرتب شده x [] اندازه n می کنیم و شاخص میانی را محاسبه می کنیم.

• if (key == x [mid]): ما مقدار هدف را پیدا کرده ایم و شاخص میانی را برمی گردانیم.
• if (کلید< X[mid]): We search for the key in the left subarray.
• If (key >X [MID]): ما کلید را در زیر مجموعه سمت راست جستجو می کنیم.

در یک روش مشابه ، ما جستجو می کنیم تا زمانی که کلید (جستجوی موفقیت آمیز) پیدا شود یا اندازه Subarray به 0 کاهش یابد (جستجوی ناموفق). ایده اصلی ساده است: در هر مرحله از فرآیند ، ما به طور مداوم فاصله جستجو یا اندازه ورودی را به نصف کاهش می دهیم.

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

فرض کنید ما برای جستجوی کلید داده شده در آرایه مرتب شده از یک عملکرد باینری (x [] ، l ، r ، کلید) استفاده می کنیم. در اینجا L و R به عنوان شاخص انتهای سمت چپ و راست زیر زیر مجموعه در آرایه x []. ما با l = 0 و r = n - 1 شروع می کنیم.

تقسیم قسمت

• ما شاخص میانی یعنی MID = L + (R - L)/2 را محاسبه می کنیم
• if (x [mid] == کلید): ما مقدار را میانی می کنیم.

توجه: چرا ما از معادله (L + R)/2 برای محاسبه شاخص میانی استفاده نکردیم؟در اینجا دلیل وجود دارد: عملاً ، برای مقدار بزرگ شاخص چپ و راست ، مقدار (L + R) ممکن است از محدوده اعداد صحیح نوع داده (حتی اگر L و R در محدوده باشد) فراتر رود. این می تواند منجر به سرریز عدد صحیح برای آرایه های بسیار بزرگ شود. برای حل این مشکل ، می توانیم از معادله Mid = L + (R - L)/2 برای رفع خطای سرریز عدد صحیح استفاده کنیم. این مرجع فوق العاده را برای درک بهتر دنبال کنید: https://ai. googleblog. com/2006/06/extra-extra-read-all-about-it-nearly. html

قسمت فاتح

• If (X[mid] >کلید): کلید نباید در نیمه سمت راست آرایه وجود داشته باشد. بنابراین ما به صورت بازگشتی کلید را در نیمه سمت چپ آرایه یعنی باینریس جستجوی (X ، L ، اواسط - 1 ، کلید) جستجو می کنیم.
• if (x [mid]< key): The key must not be present in the left half of the array. So we recursively search for the key in the right half of the array i.e. binarySearch(X, mid + 1, r, key) .
• به طور مشابه ، بر اساس مقایسه با ارزش متوسط ، ما به جستجوی بازگشتی در نیمه چپ یا راست آرایه ادامه می دهیم تا اینکه کلید را پیدا کنیم یا به مورد پایه برسیم.

قسمت را با هم ترکیب کنید

این یک مرحله بی اهمیت است زیرا پس از مقایسه عنصر میانی ، یک راه حل زیرنویس (یا نیمه چپ یا راست) شاخص را برمی گرداند (در صورت وجود کلید موجود است) یا بازگش ت-1 (اگر کلید موجود نیست). نیازی به ترکیب راه حل برای مشکلات فرعی نیست. فکر!

مورد پایه

The base case would be the scenario when the left index crosses the right index or the subarray size shrinks to zero i.e. if (l >r) ، م ا-1 برمی گردیم. این مورد جستجوی ناموفق است. به عبارت دیگر: این آخرین مرحله بازگشت یا کوچکترین نسخه زیرنویس است.

جستجو باینری بازگشتی شبه کد

اجرای تکراری الگوریتم جستجوی باینری

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

• If (X[mid] >کلید): ما باید کلید را در نیمه سمت چپ آرایه جستجو کنیم. برای آرایه سمت چپ ، شاخص سمت چپ یکسان خواهد بود ، اما شاخص سمت راست اواسط - 1 خواهد بود.
• if (x [mid]< key): We need to search the key in the right half of the array. For the right array, the right index would be the same, but the left index would be mid + 1 .
• Similarly, after comparison with the mid-value, we continue searching iteratively on either the left or right half of the array, again finding the middle element and proceeding as before. Loop will stop if we either find the key (successful search) or if the size of the subarray shrinks to zero ( l >r) ، که یک مورد از جستجوی ناموفق است). به عبارت دیگر: حلقه تا (L ادامه خواهد یافت

شبه کد الگوریتم جستجوی باینری تکراری

تجزیه و تحلیل پیچیدگی زمانی

After each comparison, the input size decreases by half. Initially, we have n elements, then we have n/2 elements after the 1st comparison, n/4 elements after the 2nd comparison, and so on. The worst-case situation will occur when we reach the base case (unsuccessful search) i.e. n -> n/2 -> n/4 -> …… 1 ->جستجوی ناموفق

• Suppose we reach the base case after the k number of steps => n/2^k = 1 => n = 2^k =>k = log2n. در کلمات ساده: پس از تعداد مراحل log2n ، الگوریتم به مورد پایه خود می رسد.
• در هر مرحله از بازگشت ، عملیات O (1) را انجام می دهیم. بنابراین بدترین حالت پیچیدگی زمان جستجوی باینری = log2n * o (1) = o (logn).

ایده دیگری از تحلیل!

For the clear picture, let’s assume for the moment that the size of the array is a power of 2 i.e. n = 2^k =>k = log2n. اکنون وقتی هر بار عنصر میانی را مقایسه می کنیم ، اندازه زیر مجموعه ها را به نصف برش می دهیم.

در ابتدا ، اندازه Subarray 2^k است. بعد از مرحله 1 ، اندازه زیر ساینده 2^(k - 1) خواهد بود و بعد از مرحله دوم ، اندازه زیر ساینده 2^(k - 2) و غیره خواهد بود. پس از تعداد K یا Log2N مراحل ، ما به صحنه یک آرایه عنصر واحد خواهیم رسید. اکنون در مرحله بعدی ، ما به پرونده پایه خواهیم رسید.

بنابراین همه با هم می توانیم حداکثر K + 1 یا Log2n + 1 مراحل را در بدترین حالت داشته باشیم. در هر مرحله ، ما یک کار ثابت را انجام می دهیم: محاسبه نقطه میانی و یک عمل مقایسه. به طور کلی ، هنگامی که به اندازه آرایه n داده می شود ، عملیات C (log2 n + 1) را در بدترین حالت انجام می دهیم. بنابراین جستجوی باینری بدترین حالت پیچیدگی زمان = O (logn)

تجزیه و تحلیل با استفاده از قضیه استاد

Let’s assume that T(n) is the worst-case time complexity of the binary search for n elements. When we have n >0 ، ما می توانیم پیچیدگی های زمانی را به شرح زیر تجزیه کنیم:

• تقسیم قسمت: پیچیدگی زمانی این قسمت o (1) است زیرا ما فقط شاخص میانی آرایه را محاسبه می کنیم ، که زمان ثابت طول می کشد.
• قسمت فاتح: ما به صورت بازگشتی در حال حل یک زیرنویس با اندازه N/2 هستیم. بنابراین پیچیدگی زمان کلی قسمت فاتح t (n/2) است.
• قسمت ترکیب: همانطور که در بالا ذکر شد ، این قسمت بی اهمیت است. بنابراین پیچیدگی زمان قسمت ترکیبی o (1) است.

For calculating the T(n), we need to add the time complexities of the divide, conquer, and combine part =>t (n) = o (1) + t (n/2) + o (1) = t (n/2) + c. در اینجا رابطه عود از پیچیدگی زمان بدترین حالت وجود دارد:

• t (n) = c ، اگر n = 1
• T(n) = T(n/2) + c, if n > 1

This recurrence relation is in the form of T(n) = aT(n/b) + O(n^k) where a ≥ 1 and b >1. ما می توانیم فکر کنیم که قضیه استاد را اعمال کنیم! سه مورد از راه حل از طریق تئوری استاد وجود دارد:

1. اگر f (n) = o (n^k) که در آن k< logb(a) then T(n) = O(n*logb(a))
2. اگر f(n) = O(n^k) که در آن k = logb(a) سپس T(n) = O(n^k * logn)
3. If f(n) = O(n^k) where k >logb(a) سپس T(n) = O(f(n))

اگر رابطه عود جستجوی دودویی و قضیه اصلی را مقایسه کنیم:

• a = 1, b = 2 where a≥1 and b>1
• f(n) = c = cn^0 = O(n^0) =>k = 0
• به طور مشابه، logb(a) = log 2(1) = 0. بنابراین، logb(a) = k = 0

عود بالا مورد دوم قضیه اصلی را برآورده می کند. بنابراین پیچیدگی زمانی T(n) = O(n^k * logn) = O(n^0 * logn) = O(logn).

تحلیل پیچیدگی فضا

پیچیدگی فضای جستجوی دودویی به اجرای آن بستگی دارد. در رویکرد تکراری، از فضای اضافی ثابت استفاده می کنیم تا پیچیدگی فضا O(1) باشد. در روش بازگشتی، پیچیدگی فضا به اندازه پشته فراخوان بازگشتی بستگی دارد.

• اندازه پشته تماس بازگشتی به تعداد کل سطوح در درخت بازگشت یا ارتفاع درخت بازگشت بستگی دارد.
• ارتفاع درخت بازگشتی = logn + 1. از بالا به پایین تا حالت پایه، ما فقط یک تماس بازگشتی در هر سطح داریم! بنابراین پیچیدگی فضایی الگوریتم جستجوی باینری بازگشتی = O(log n)

داستانی جالب از تاریخ!

در اینجا یادداشتی از جان بنتلی از کتاب برنامه نویسی مروارید آمده است:

من جستجوی باینری را در دوره‌های آزمایشگاه Bell و IBM اختصاص داده‌ام. برنامه نویسان حرفه ای چند ساعت فرصت داشتند تا توضیحات آن را به یک برنامه به زبان مورد علاقه خود تبدیل کنند. شبه کد سطح بالا خوب بود. در پایان زمان مشخص شده، تقریباً همه برنامه نویسان گزارش دادند که کد صحیح کار را دارند. سپس سی دقیقه وقت می‌گذاریم تا کد آنها را بررسی کنیم، کاری که برنامه‌نویسان با موارد آزمایشی انجام دادند. در چندین کلاس و با بیش از صد برنامه نویس، نتایج کمی متفاوت بود: نود درصد برنامه نویسان اشکالاتی را در برنامه های خود پیدا کردند (و من همیشه به درستی کدی که هیچ باگی در آن یافت نشد متقاعد نشدم). من شگفت زده شدم: با توجه به زمان کافی، تنها حدود ده درصد از برنامه نویسان حرفه ای توانستند این برنامه کوچک را به درستی اجرا کنند.

ایده های انتقادی برای فکر کردن!

• اکثر برنامه نویسان در تعریف شرط پایه کد بازگشتی یا شرایط خروج از کد تکراری خطا می کنند. فکر!
• ما می‌توانیم از ایده جستجوی دودویی برای حل چندین مشکل کدگذاری استفاده کنیم که در آن آرایه دارای خاصیت ترتیبی مشابه آرایه مرتب‌شده است. به عنوان مثال، برای یک مقدار مشخص، چگونه می‌توانیم جستجوی باینری را تغییر دهیم تا تعداد عناصر کوچک‌تر، مقدار کوچک‌ترین عنصر بعدی، همه نزدیک‌ترین همسایگان و غیره را بیابیم؟
• حتی اگر عناصر تکراری در آرایه وجود داشته باشد، جستجوی باینری ممکن است شاخصی را برگرداند که برابر با مقدار هدف باشد. با این حال، همیشه اولین یا آخرین رخداد عنصر را بر نمی گرداند. آیا می توانیم الگوریتم جستجوی باینری را برای یافتن اولین یا آخرین رخداد عنصر تغییر دهیم؟فکر!
• جستجوی دودویی ممکن است روی آرایه های مرتب شده به طور موثر کار نکند، زمانی که درج و حذف اغلب با جستجو اتفاق می افتد. عملیات درج و حذف در مورد آرایه مرتب شده به زمان O(n) نیاز دارد. فکر!
• جستجوی نمایی تغییری از الگوریتم جستجوی دودویی برای آرایه نامحدود است، یعنی آرایه ای که راست ترین مرز برای آن ناشناخته است. همچنین می‌تواند روی آرایه محدود کار کند، اما کارایی آن تنها در صورتی بهتر از جستجوی باینری است که مقدار هدف نزدیک به شروع آرایه باشد. فکر!
• در یک BST، عناصر به ترتیب مرتب شده ساختار درختی مرتب شده اند و هر داده را می توان با استفاده از ایده ای شبیه به جستجوی دودویی جستجو کرد. درج و حذف کاملاً کار می کند و به زمان متوسط O(logn) سریعتر از درج و حذف آرایه های مرتب شده نیاز دارد.

مفاهیمی برای بررسی بیشتر

• جستجوی نمایی، جستجوی درون یابی

مشکلات مبتنی بر جستجوی باینری برای تمرین

لطفاً در صورت مشاهده موارد نادرست در پیام زیر بنویسید یا می خواهید اطلاعات بیشتری را به اشتراک بگذارید. از یادگیری لذت ببرید، از الگوریتم ها لذت ببرید!