close
دانلود فیلم
عنصر

بيشترين اندازه آرايه

به دليل مدلی که حافظه کار می کند متغيری با بيشتر از 64KB فضای اشغالی نمی توان داشت. اگر هيچ متغير ديگری در برنامه وجود نداشته باشد يک آرايه يک بعدی حداکثر می تواند 64KB فضا اشغال کند. البته بعضی از سيستم عامل ها اين محدوديت را ندارند.

فضای مورد نياز برای ذخيره آرايه به تعداد کل عناصر و تعداد بايت های هر عنصر بستگی دارد. برای محاسبه فضای يک آرايه تعداد عناصر آن در تعداد بايت های نوع داده عناصر ضرب می شود.


مثال. ميزان فضائی که يک آرايه با 500 عنصر از نوع float اشغال می کند برابر با 500×4=2000 بايت است.


فضای يک آرايه را توسط عماگر ()sizeof هم می توان بدست آورد.


نکته. ارسال آرایه به توابع همیشه به صورت مرجع است.

جستجوی دودوئی

الگوریتم جستجوی دودوئی (binary search algorithm) روشی برای جستجوی یک مقدار درون یک لیست مرتب است. عنصر وسط لیست انتخاب شده و با آرگومان جستجو مقایسه می شود تا تعیین شود از آن بزگتر، کوچکتر یا مساوی است. اگر آرگومان از عنصر انتخاب شده بزرگتر باشد جستجو در نیمه پایینی و اگر کوچکتر باشد در نیمه بالائی لیست ادامه پیدا می کند.

کد بازگشتی جستجوی دودوئی به صورت زیر است:

int BinarySearch(int A, int value, int low, int high) {
  if (high < low)
    return -1    // not found
  mid = (low + high) / 2
  if (A[mid] > value)
    return BinarySearch(A, value, low, mid-1)
  else if (A[mid] < value)
    return BinarySearch(A, value, mid+1, high)
  else
    return mid    // found
}

زمان جستجو O(log n) است که زمان بهتری نسبت به جستجوی خطی است. اگر آرگومان جستجو برابر با عنصر وسط لیست باشد با یک مقایسه پیدا می شود که بهترين حالت است. در بدترین حالت به ⌊log2 n ⌋ + 1 مقايسه نياز است.

جستجوی دودوئی مثالی از یک الگوریتم تقسیم و غلبه است.

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