سلام
دو آرایه n تایی A,B حاوی اعداد حقیقی و یک عدد M داده شده ، می خواهیم دو عدد i,j را در صورت وجود i,j بین 1 تا n پیدا کنیم طوری که :
A[i]+B[j]=M
بهترین الگوریتم برای این مسئله ؟
جواب :nlgn
-----
از ایده ای که اینجا استفاده شده ، عناصر رو بدون مرتب کردن ؛
1- حلقه ای به طول n یک مجموعه universe برای عناصر B بساز
2-اگرتفاضل قدر مطلق a[i] با M در مجموعه universe بود حتما j در آرایه B هست ؛ پس با یک حلقه به طول O(n) جواب پیدا میشه
وگرنه حلقه ابتدا ++ بشه
در مورد 2 حلقه زمانی اجرا میشه که عنصر مورد نظر hit بشه وگرنه اجرا نمیشه
جوابی که داده فکر کنم از ایده ی binary search استفاده کرده!