الگوریتم جستجوی دودویی چگونه عمل می‌کند

---

الگوریتم جستجوی دودویی (Binary Search) یک الگوریتم جستجوی کارآمد برای یافتن یک عنصر خاص در یک آرایه مرتب شده است. اساس کار این الگوریتم بر مبنای تقسیم و غلبه (Divide and Conquer) است. در زیر توضیح می‌دهم که چگونه این الگوریتم کار می‌کند:

**شرط لازم:**

* آرایه باید **مرتب** باشد (صعودی یا نزولی).

**مراحل کار:**

1. **تعیین محدوده جستجو:** ابتدا، الگوریتم یک محدوده جستجو را تعریف می‌کند. این محدوده در ابتدا کل آرایه را در بر می‌گیرد.
* `low`: اندیس ابتدای محدوده (به طور معمول 0).
* `high`: اندیس انتهای محدوده (به طور معمول `length(array) - 1`).

2. **محاسبه اندیس میانی:** الگوریتم اندیس عنصر میانی محدوده جستجو را محاسبه می‌کند.
* `mid = (low + high) / 2` (یا `mid = low + (high - low) / 2` برای جلوگیری از سرریز شدن `int` در زبان‌های خاص).

3. **مقایسه با عنصر میانی:** عنصر مورد جستجو (`target`) با عنصر موجود در اندیس میانی (`array[mid]`) مقایسه می‌شود. سه حالت ممکن است رخ دهد:
* **حالت 1: `target == array[mid]`**: عنصر مورد نظر پیدا شده است. الگوریتم اندیس `mid` را برمی‌گرداند.
* **حالت 2: `target < array[mid]`**: اگر عنصر مورد نظر کوچکتر از عنصر میانی باشد، می‌دانیم که اگر عنصر در آرایه وجود داشته باشد، باید در نیمه چپ محدوده جستجو قرار داشته باشد. پس محدوده جستجو به نیمه چپ محدود می‌شود.
* `high = mid - 1`
* **حالت 3: `target > array[mid]`**: اگر عنصر مورد نظر بزرگتر از عنصر میانی باشد، می‌دانیم که اگر عنصر در آرایه وجود داشته باشد، باید در نیمه راست محدوده جستجو قرار داشته باشد. پس محدوده جستجو به نیمه راست محدود می‌شود.
* `low = mid + 1`

4. **تکرار:** مراحل 2 و 3 تا زمانی که عنصر مورد نظر پیدا شود یا محدوده جستجو خالی شود (یعنی `low > high`) تکرار می‌شوند.

5. **عدم یافتن:** اگر محدوده جستجو خالی شود و عنصر مورد نظر پیدا نشود، الگوریتم یک مقدار خاص (مثلاً -1) را برمی‌گرداند تا نشان دهد که عنصر در آرایه وجود ندارد.

**مثال:**

فرض کنید آرایه مرتب شده زیر را داریم و می‌خواهیم عدد 23 را در آن پیدا کنیم:

`array = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]`

1. `low = 0`, `high = 9`
2. `mid = (0 + 9) / 2 = 4` -> `array[4] = 16`
3. `23 > 16` -> `low = 4 + 1 = 5`
4. `low = 5`, `high = 9`
5. `mid = (5 + 9) / 2 = 7` -> `array