جستجوی دودویی (Binary Search) یکی از الگوریتمهای جستجوی مؤثر و کارآمد است که برای یافتن یک عنصر خاص در یک لیست مرتبشده استفاده میشود. الگوریتم جستجوی دودویی با مقایسه عنصر مورد نظر با عنصر میانه (middle) لیست، مسیری را پیدا میکند که بهطور پیوسته بخشهای غیرضروری از لیست را حذف میکند. این فرآیند تا زمانی که عنصر مورد نظر پیدا شود یا لیست به انتها برسد ادامه مییابد.
الگوریتم جستجوی دودویی به دلیل استفاده از تقسیم و غلبه، زمان اجرای بسیار سریعتری نسبت به جستجوی خطی دارد. زمان اجرای آن به صورت O(log n) است، در حالی که جستجوی خطی زمان اجرای O(n) دارد. این امر جستجوی دودویی را برای جستجو در مجموعه دادههای بزرگ بسیار کارآمد میکند.
الگوریتم جستجوی دودویی تنها بر روی دادههای مرتبشده (sorted data) کار میکند. اگر دادهها به ترتیب صعودی یا نزولی مرتب نشده باشند، باید ابتدا آنها را مرتب کرد تا بتوان از جستجوی دودویی استفاده کرد.
در زبانهای برنامهنویسی مختلف مانند Python، Java و C++، جستجوی دودویی معمولاً به شکل زیر پیادهسازی میشود. در اینجا یک مثال از پیادهسازی جستجوی دودویی در Python آورده شده است:
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1 # عنصر پیدا نشددر این مثال، تابع binary_search دو ورودی دریافت میکند: یک آرایه مرتبشده و عنصر هدف که باید در آرایه جستجو شود. ابتدا مقادیر low و high تعیین میشوند که نشاندهنده ابتدای و انتهای آرایه هستند. سپس در هر مرحله از حلقه، عنصر میانه بررسی میشود و بسته به مقایسه آن با عنصر هدف، بخشهایی از آرایه نادیده گرفته میشود. اگر عنصر پیدا شود، اندیس آن بازگردانده میشود؛ در غیر این صورت، تابع -1 را باز میگرداند که نشاندهنده عدم وجود عنصر در آرایه است.
در زبان Java، جستجوی دودویی به صورت زیر پیادهسازی میشود:
public class BinarySearch {
public static int binarySearch(int[] arr, int target) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1; // عنصر پیدا نشد
} }در اینجا نیز همانطور که در Python مشاهده میشود، تابع binarySearch آرایه مرتبشده و عنصر هدف را به عنوان ورودی دریافت کرده و الگوریتم جستجوی دودویی را اجرا میکند.
الگوریتم جستجوی دودویی به دلیل کارایی بالای خود در جستجو در مجموعههای داده بزرگ، در بسیاری از سیستمها و برنامهها بهویژه در جستجو در پایگاهدادهها و ساختارهای دادهای مانند درختها و لیستهای مرتبشده به کار میرود.
برای اطلاعات بیشتر، میتوانید از سایت saeidsafaei.ir و اسلایدهای محمد سعید صفایی بهرهبرداری کنید.
در این مبحث، به مقدمهای بر برنامهنویسی پرداخته و مفاهیم اساسی آن شامل تعریف برنامهنویسی، اهمیت برنامهنویسی، روشهای ترجمه کد، انواع زبانهای برنامهنویسی، و مهارتها و محیطهای برنامهنویسی بررسی میشود. هدف این جلسه، آشنایی با اصول پایهای برنامهنویسی و درک نحوه انتخاب زبان و محیط مناسب برای نوشتن برنامههای کاربردی است.
دوقلوهای دیجیتال به مدلسازی دقیق سیستمهای فیزیکی بهصورت دیجیتال برای شبیهسازی، نظارت و پیشبینی رفتار آنها گفته میشود.
عدد به مجموعهای از ارقام گفته میشود که با توجه به موقعیت آنها در سیستم عددی، مقدار مشخصی دارند.
هوش مصنوعی جغرافیایی به استفاده از الگوریتمهای هوش مصنوعی برای تحلیل و پردازش دادههای جغرافیایی و مکانی اطلاق میشود.
ترجمه آدرسهای IP خصوصی به آدرسهای عمومی برای استفاده در اینترنت.
قسمتی از کامپیوتر است که وظیفه پردازش دادهها را بر عهده دارد. این بخش معمولاً به عنوان مغز کامپیوتر شناخته میشود.
پورتهایی که برای اتصال دستگاههای کاربری به سوئیچها استفاده میشوند و به یک VLAN خاص تعلق دارند.
یکپارچگی هوش مصنوعی در پردازش ابری به استفاده از مدلهای هوش مصنوعی برای تجزیه و تحلیل دادهها در سرویسهای ابری اطلاق میشود.
رباتیک خودمختار به رباتهایی اطلاق میشود که قادر به انجام وظایف پیچیده بدون نیاز به دخالت انسان هستند.
تحلیلهای زمان واقعی به تجزیه و تحلیل و پردازش دادهها بهطور همزمان با وقوع آنها گفته میشود.
اتوماتیکسازی فرآیندهای رباتیک (RPA) به استفاده از رباتها برای انجام وظایف تکراری در محیطهای تجاری اشاره دارد.
سیستمهای تحویل خودران به وسایل نقلیه و رباتهایی اطلاق میشود که بهطور خودکار کالاها را به مقصد ارسال میکنند.
چگونگی چیدمان فیزیکی و منطقی اجزای شبکه که در آن نحوه اتصال گرهها و نحوه انتقال دادهها توصیف میشود.
ماتریس یک نوع آرایه دو بعدی است که برای انجام عملیاتهای ریاضی و جبر خطی به کار میرود.
نرمافزارها شامل برنامهها و دادههای مرتبط هستند که سیستم کامپیوتری آنها را پردازش میکند.
الگوریتم مرتبسازی حبابی سادهترین الگوریتم مرتبسازی است که عناصر مجاور را مقایسه کرده و در صورت لزوم جابهجا میکند.
نوع دادهای است که برای ذخیرهسازی اعداد اعشاری و محاسبات دقیقتری استفاده میشود.
پهنای باند اختصاصی به یک کاربر یا دستگاه که برای آن دستگاه بهطور اختصاصی تخصیص داده میشود.
تابع درونخطی تابعی است که کد آن به جای فراخوانی معمولی مستقیماً در محل فراخوانی قرار میگیرد، که معمولاً برای توابع ساده و کوتاه استفاده میشود.
عملگرهای مقایسهای برای مقایسه دو مقدار و تعیین روابط آنها مانند بزرگتر از، کوچکتر از و مساوی استفاده میشوند.
تمام سیستمهای عضو شبکه به صورت حلقه ای به یکدیگر متصل میشوند و دادهها در جهت عقربههای ساعت شروع به گردش میکنند تا به مقصد برسند.
رباتیک شناختی به استفاده از رباتها برای شبیهسازی فرایندهای شناختی انسانی مانند درک، تصمیمگیری و یادگیری اطلاق میشود.
تبدیل عدد از مبنای دودویی به ده که هر رقم در مبنای دو را با ضرب در 2 به توان جایگاه آن محاسبه میکنیم.
روش دسترسی به رسانه که در آن از برخورد جلوگیری میشود، بهویژه در شبکههای بیسیم مانند Wi-Fi.
لیست پیوندی دوطرفه یک نوع خاص از لیست پیوندی است که هر عنصر در آن به دو عنصر قبلی و بعدی خود اشاره دارد.
دستورالعملی گام به گام برای حل یک مشکل خاص است. الگوریتمها نقش مهمی در برنامهنویسی و حل مسائل کامپیوتری دارند و میتوانند به صورت دستی یا با استفاده از زبانهای برنامهنویسی مختلف پیادهسازی شوند.
گراف وزنی گرافی است که در آن به هر یال یک وزن یا هزینه اختصاص داده میشود.
دیفای به سیستمهای مالی غیرمتمرکز اشاره دارد که با استفاده از فناوری بلاکچین ایجاد میشوند.
رمزنگاری دیجیتال به استفاده از الگوریتمها برای امنسازی دادهها و جلوگیری از دسترسی غیرمجاز اطلاق میشود.
عملگر یا دستور برک برای خاتمه دادن به یک حلقه یا فرآیند در زمانی خاص استفاده میشود.
غلبه کوانتومی به توانایی سیستمهای کوانتومی در حل مسائل پیچیدهای اطلاق میشود که برای رایانههای کلاسیک غیرممکن است.
دستگاههای خروجی مانند چاپگر و مانیتور که اطلاعات پردازششده را از کامپیوتر به کاربر نمایش میدهند.
وزن یا مقدار هر رقم در سیستمهای عددی که با توجه به موقعیت آن در عدد تغییر میکند. به عنوان مثال در سیستم دهدهی، هر رقم با پایههای مختلف (ده به توان اندیس) ضرب میشود.
عملگر یا دستور کانتینیو برای ادامه دادن به مرحله بعدی در یک حلقه یا فرایند استفاده میشود.
محاسبات عصبیشکل به استفاده از سیستمهایی اطلاق میشود که از ساختارهای مشابه مغز انسان برای پردازش دادهها استفاده میکنند.
ارائه سازماندهی فرآیندهای رباتیک به استفاده از رباتها برای هماهنگی و مدیریت فرآیندهای مختلف در محیطهای تجاری اطلاق میشود.
