جستجوی خطی و باینری برای عناصر در یک آرایه


جستجوی آرایه خطی
اغلب اوقات شما نیاز دارید که مقدار معینی را در یک آرایه پیدا کنید یا گزارش دهید که در آنجا وجود ندارد. برای انجام این کار، باید تمام عناصر آرایه را از اول تا آخر بررسی کنید. به محض اینکه عنصری برابر با مقدار داده شده X پیدا شد، جستجو باید پایان یابد و نتیجه نمایش داده شود. چنین الگوریتمی خطی
نامیده می شود
یک الگوریتم خطی برای یافتن حداکثر (حداقل) عنصر یک آرایه استفاده می شود. این نیز یک الگوریتم جستجو است. اما در اینجا مجبوریم تا انتهای آرایه برویم، زیرا لازم است همه عناصر را با مقدار حداکثر (حداقل) فعلی مقایسه کنید و اگر عنصر فعلی بزرگتر (کمتر) از مقدار حداکثر (حداقل) است، مقدار حداکثر (حداقل) را جایگزین کنید. 
 

Training problem

جستجوی خطی - به دنبال حداکثر

روش دیگری برای حل این مشکل امکان پذیر است. اگر مقدار مورد نیاز پیدا شد، می‌توانید از خروجی اولیه از حلقه استفاده کنید. 
در C++، دستور break برای خارج شدن از یک حلقه استفاده می شود.

Training problem

جستجوی خطی - 3 خروج زودهنگام از حلقه

جستجوی باینری
جستجوی باینری (یا باینری) یک الگوریتم جستجوی کارآمد است و سریعتر از جستجوی خطی است. به عنوان مثال، برای یک آرایه از 1024 عنصر، جستجوی خطی در بدترین حالت (زمانی که عنصر مورد نظر در آرایه نباشد) تمام 1024 عنصر را پردازش می کند، اما کافی است 10 عنصر را با جستجوی باینری پردازش کنید. این نتیجه به این دلیل به دست می‌آید که پس از مرحله اول حلقه، ناحیه جستجو به 512 عنصر کاهش می‌یابد، پس از – تا 256 و غیره.
 
معایب چنین الگوریتمی نیاز به ترتیب داده ها و همچنین امکان دسترسی به هر عنصر داده در یک زمان ثابت (مستقل از مقدار داده) است. بنابراین، الگوریتم نمی تواند روی آرایه های نامرتب کار کند.
 
الگوریتم
  1. عنصر میانی A[c] را انتخاب کنید و با X مقایسه کنید.
  2. اگر X = A[c] پیدا شد (توقف کنید).
  3. اگر X < A[c]، در نیمه اول بیشتر جستجو کنید.
  4. اگر X > A[c]، به نیمه دوم نگاه کنید.
     
اجرا
L = 0; R=N; // بخش اولیه در حالی که (L < R - 1) { c = (L + R) / 2; // وسط را پیدا کرد اگر (X < A[c] ) // فشرده سازی بخش R=c; دیگر L = c; } اگر (A[L] == X) cout << "الف» << L<< "]=" << ایکس؛ دیگر cout << "پیدا نشد";

جایی که:
A - آرایه منبع،
N - اندازه آرایه،
X - شماره جستجو شده،

پیاده سازی های دیگر امکان پذیر است.
به عنوان مثال، استفاده از یک خروج زودهنگام از حلقه L = 0; R = N - 1; در حالی که (R >= L) { c = (L + R) / 2; اگر (X == A[c]) { nX = c; زنگ تفريح؛ } اگر (X < A[c]) R = وسط - 1; اگر (X > A[c]) L = وسط + 1; } اگر (nX < 0) cout << "پیدا نشد"; دیگر cout << "الف» << nX<< "]=" << X;

Training problem

جستجوی باینری

مقایسه الگوریتم‌های جستجوی خطی و باینری بر اساس تعداد مقایسه‌ها
 
نمونه‌ها
<سر> <بدن>
# جستجوی خط جستجوی باینری
2 2 2
16 16 5
1024 1024 11
1048576 1048576 21

مزیت مرتب سازی باینری این است که سریعتر است.
معایب- یک آرایه از پیش مرتب شده لازم است.

 

Training problem

اجرای جستجوی باینری