====== الگوریتم شناسایی میانه ======
یافتن میانه یا $\frac{n}{2}$ امین عنصر از نظر کوچکی در یک آرایه حالت خاصی از [[آموزش:الگوریتم:الگوریتم_تصادفی_شناسایی_عنصر_k_ام|الگوریتم شناسایی عنصر kام]] می‌باشد. پیدا کردن میانه با زمان بهینه در الگوریتم [[آموزش:الگوریتم:مرتب‌سازی_سریع|مرتب‌سازی سریع]] می‌تواند مرتبه زمانی الگوریتم را در بدترین حالت به
$O(n\log n)$
برساند. با توجه به این که الگوریتم شناسایی عنصر kام از $O(n)$ می‌باشد و این بهترین مرتبه زمانی ممکن است (حداقل یک بار باید آرایه خوانده بشود) بنابراین بهترین الگوریتم شناسایی میانه نیز از همین مرتبه زمانی است. الگوریتم‌های دیگری مانند میانه‌ی میانه‌ها وجود دارند که تنها تضمین می‌کنند جواب مسئله در بازه‌ی خاصی از آرایه قرار دارد، مثلاً بین مرتبه‌ی آماری $\frac{3n}{10}$ و $\frac{7n}{10}$ قرار دارد. این الگوریتم‌ها تصادفی نیستند و با توجه به این که استفاده از عنصر $\frac{n}{k}$ام به جای عنصر $\frac{n}{2}$ام تنها مبنای لگاریتم در تابع زمان را تغییر می‌دهد، اردر الگوریتم ثابت می‌ماند و از آن‌ها نیز می‌توان برای این کار استفاده کرد. این کار در عمل صورت نمی‌گیرد، امّا در تئوری استفاده نکردن از بیت‌های تصادفی و قطعیت کامل الگوریتم ارزشمند است.

===== مراجع =====

  * [[https://en.wikipedia.org/wiki/Median_of_medians|میانه‌ی میانه‌ها - ویکی‌پدیا]]