باینری سرچ

توضیحات

مسئله

بازی ای دو نفره داریم که دو فرد \(A\) و \(B\) در آن بازی میکنند. ابتدا \(A\) یک عدد طبیعی از \(1\) تا \(10^{9}\) انتخاب میکند. سپس \(B\) بایستی عدد انتخاب شده را حدس بزند. او حداکثر \(40\) بار فرصت حدس زدن دارد. هربار که \(B\) عددی را حدس بزند. \(A\) به او میگوید که عدد حدس زده شده کوچکتر از عدد انتخاب شده هست یا نه؛ به عبارتی اگر \(A\) عدد \(k\) را انتخاب کرده باشد و \(B\) عدد \(x\) را حدس زده باشد. اگر \(x < k\) باشد آنگاه نفر \(A\) میگوید بله در غیر این صورت خیر.

همچنین \(B\) یک فرصت برای حدس نهایی دارد که اگر حدس او با عدد انتخاب شده یکی باشد، برنده شده در غیر این صورت میبازد. حال ما بایستی به عنوان فرد \(B\) برنده بازی بشویم.

راه حل

دو متغیر \(L\) و \(R\) را تعریف میکنیم. ابتدا \(L = 0\) و \(R = 10^{9}\) قرار میدهیم. میدانیم \(L < k\) و \(k \leq R\) است. حال متغیر \(mid\) را تعریف میکنیم و آنرا برابر با \(\lfloor \frac{L + R}{2} \rfloor\) قرار میدهیم. حال عدد \(mid\) را از \(A\) میپرسیم اگر گفت که عدد داده شده از \(k\) کوچکتر است، \(L = mid\) قرار میدهیم در غیر این صورت \(R = mid\) قرار میدهیم. حال به ازای \(L\) و \(R\) جدید میدانیم \(L < k\) و \(k \leq R\) است.

این روند را ادامه میدهیم تا زمانی که \(L+1 = R\) شود. سپس \(R\) را به عنوان حدس نهایی خروجی میدهیم.

تعداد عملیات های راه حل

فرض کنیم \(len = R - L\) باشد. پس از هر بار پرسش و تغییر مقادیر \(L\) و \(R\) میتوان گفت اگر مقدار جدید \(len\) را برابر با \(len^{\prime}\) در نظر بگیریم \(len^{\prime} \leq \lceil \frac{len}{2} \rceil\) است.

اثبات

\(mid = \lfloor \frac{L + R}{2} \rfloor = \lfloor \frac{2 * L + len}{2} \rfloor = L + \lfloor \frac{len}{2} \rfloor\)

اگر \(R = mid\) شود: \(len^{\prime} = L + \lfloor \frac{len}{2} \rfloor - L = \lfloor \frac{len}{2} \rfloor\)

اگر \(L = mid\) شود: \(len^{\prime} = L + len - (L + \lfloor \frac{len}{2} \rfloor) = len - \lfloor \frac{len}{2} \rfloor = \lceil \frac{len}{2} \rceil\)

حال چون هر بار مقدار \(len\) به حداکثر \(\lceil \frac{len}{2} \rceil\) تبدیل میشود و ما وقتی \(len = 1\) شود عملیات هارا تمام میکنیم، حداکثر \(\lceil log(10^{9}) \rceil\) پرسش انجام میدهیم (‌مقدار \(len\) در ابتدا برابر با \(10^{9}\) است.) که برابر با \(30\) پرسش میشود.

تعریف کلی

فرض کنیم تابع \(f\) را داریم که عدد صحیح ورودی میگیرد. میدانیم عدد صحیح \(y\) ای وجود دارد به طوری که به ازای هر عدد صحیح \(x\):

• \(f(x) = 0\) است اگر و تنها اگر \(x < y\)

• \(f(x) = 1\) است اگر و تنها اگر \(y \leq x\)

همچنین میدانیم دو عدد صحیح \(L\) و \(R\) وجود دارند به طوری که \(L < y\) و \(y \leq R\) است.

میخواهیم عدد \(y\) را پیدا کنیم. برای اینکار دقیقا مانند سوال بالا میتوان رفتار کرد و در \(O(log(R - L))\) عملیات مسئله را حل کرد.

کد

در این جا کدی مربوط به سوالی که حل کردیم را مشاهده میکنیم.

int ask(int x){ // (1)!

    cout << "Ask: " << x << endl;

    int res;
    cin >> res;

    return res;
}

int main(){

    int L = 0, R = 1'000'000'000; // (2)!

    while(L + 1 < R){
        int mid = (L + R) >> 1; // (3)!
        if (ask(mid) == 0) L = mid;
        else R = mid;
    }

    cout << "Hads nahaei: " << R << endl;
}

1. تابع ask معادل تابع \(f(x)\) در حالت کلی مسئله است که به ازای مقادیر کوچکتر از عدد مورد نظر \(0\) و در غیر اینصورت \(1\) میدهد.

2. مقدار \(L\) و \(R\) که میدانیم قطعا عدد مورد نظر بزرگتر اکید از \(0\) و کوچکتر مساوی \(10^{9}\) است.

3. در اینجا میتوان ثابت کرد این عملیات معادل کف تقسیم بر دو میباشد.

باینری سرچ پیوسته

میتوان در تمامی تعاریف گفته شده به جای عدد صحیح، عدد حقیقی قرار داد. مشکلی که پیش خواهد آمد این است که در این صورت الگوریتم شرط پایان ندارد‌ (\(L + 1 = R\)).

اما نکته ای که وجود دارد این است که در سوال های مربوطه همواره با تعدادی رقم اعشار قرار است جواب سوال را خروجی بدهیم (‌برای مثال با \(6\) رقم اعشار).

پس میتوان شرط جدیدی برای پایان الگوریتم گذاشت‌ (\(R - L > 0.000001\)) . اما به خاطر خطا های محاسباتی در اعشار در ++C این روش زیاد مناسب نیست.

میتوان تا جایی باینری سرچ را ادامه داد تا مطمعن باشیم مقدار \(L\) و \(R\) تا \(6\) رقم اعشار دقیق شده باشد. میتوان با استدلالی مشابه حالت گسسته باینری سرچ گفت تعداد این عملیات ها برابر با \(\lceil log((R - L) * 10^{6}) \rceil\) میباشد

کد این دو روش به شکل زیر میباشد:

• روش اول:

int ask(double x) {

    cout << "Ask: " << x << endl;

    int res;
    cin >> res;

    return res;
}

int main() {
    cout << fixed << setprecision(6); // (1)!

    double L = 0, R = 1e9;
    double eps = 0.000001; // (2)!

    while(R - L > eps){
        double mid = (L + R) / 2; // (3)!
        if (ask(mid) == 0) L = mid;
        else R = mid;
    }

    cout << "Hads nahaei: " << R << endl;
}

1. به این شیوه اعداد اعشاری را با \(6\) رقم اعشار خروجی میدهیم.

2. دقت اعشاری که قرار است خروجی بدهیم.

3. در اینجا چون با اعداد اعشاری سر و کار داریم دیگر از عملگر شیفت به راست (‌ << ) نمیتوانیم استفاده کنیم.

حال کد روش دوم را میبینیم.

روش دوم:

int ask(double x) {

    cout << "Ask: " << x << endl;

    int res;
    cin >> res;

    return res;
}

int main() {
    cout << fixed << setprecision(6);

    double L = 0, R = 1e9;

    for (int i = 1; i <= 60; i++){ // (1)!
        double mid = (L + R) / 2;
        if (ask(mid) == 0) L = mid;
        else R = mid;
    }

    cout << "Hads nahaei: " << R << endl;
}

1. میدانیم \(\lceil log(10^{9} * 10^{6}) \rceil \leq 50\) میباشد پس با تعداد بار پرسیدن بیشتر مساوی \(50\) بار از دقت جواب اطمینان خواهیم داشت.

ترنری سرچ

تعریف کلی

تابعی به نام \(f\) داریم. میدانیم دو عدد صحیح \(y\) و \(z\) وجود دارد که \(y \leq z\) و به طوری که به ازای هر عدد صحیح \(x\):

• \(f(x) > f(x+1)\) است اگر و تنها اگر \(x < y\)

• \(f(x) = f(x+1)\) است اگر و تنها اگر \(y \leq x < z\)

• \(f(x) < f(x+1)\) است اگر و تنها اگر \(z \leq x\)

همچنین دو عدد \(L\) و \(R\) را داریم به طوری که \(L < y\) و \(z \leq R\)، میخواهیم عدد k را پیدا کنیم به طوری که \(y \leq k \leq z\) باشد.

راه حل

تابع \(g(x)\) را تعریف میکنیم به شکل زیر:

• \(g(x) = 1\) اگر و تنها اگر \(f(x) \leq f(x+1)\)

• \(g(x) = 0\) اگر و تنها اگر \(f(x) > f(x+1)\)

میتوان مشاهده کرد که تابع \(g(x)\) باینری سرچ پذیر است و مقداری که به ما میدهد برابر با \(y\) است که شرایط \(k\) را دارد پس در \(O(log(R-L))\) عملیات مسئله حل میشود.

ترنری سرچ پیوسته

باز میتوان به جای استفاده از اعداد صحیح مسئله را به اعداد حقیقی گسترش داد.

مهم

تعاریف در حالت حقیقی دستخوش تغییرات مهمی میشود ولی با نگاه کلی میتوان دید مشابه حالت قبل است.

به ازای تابع \(f\) میدانیم دو عدد \(y\) و \(z\) که \(y \leq z\) وجود دارند به طوری که به ازای هر دو عدد \(a\) و \(b\) که \(a < b\) است:

• اگر \(b < y\) باشد، آنگاه \(f(a) > f(b)\) است.
• اگر \(y \leq a\) و \(b \leq z\) باشد، آنگاه \(f(a) = f(b)\) است.
• اگر \(z \leq a\) باشد، آنگاه \(f(a) < f(b)\) است.

باز فرض میکنیم با \(6\) رقم اعشار جواب را میخواهیم محاسبه کنیم. یک روش این است که همان روش حالت گسسته مسئله را اجرا کنیم و مقدار \(g(x)\) به جای اینکه به \(f(x)\) و \(f(x+1)\) وابسته باشد به \(f(x)\) و \(f(x+0.000001)\) باشد‌ (زیرا میخواهیم با این دقت جواب را محاسبه کنیم). پس باز با باینری سرچ مسئله را حل کنیم. در این وضعیت دوباره ممکن است به همان مشکل خطای محاسبه اعداد اعشاری در ++C برخورده میکنیم.

در این روش ابتدا دو متغیر \(midl\) و \(midr\) تعریف میکنیم به طوری که \(midl = \frac{2 * L + R}{3}\) و \(midr = \frac{L + 2 * R}{3}\) باشد. (میتوان ثابت کرد اگر بازه \(L\) تا \(R\) را به \(3\) بازه مساوی تقسیم کنیم دو سر دیگر این سه بازه \(midl\) و \(midr\) خواهد بود. اثبات این موضوع با شما :) )

حال دو حالت خواهیم داشت:

• اگر \(f(midl) \geq f(midr)\) آنگاه \(L = midl\) قرار میدهیم.

• اگر \(f(midl) < f(midr)\) آنگاه \(R = midr\) قرار میدهیم.

فرض کنیم حالت اول رخ داده است. میخواهیم بگوییم با فرض اینکه قبل از انجام عملیات عدد \(k\) ای میان \(L\) و \(R\) وجود داشت، بعد از عملیات نیز هنوز عددی میان \(L\) و \(R\) هست که خاصیت مورد نظر برای عدد \(k\) را داشته باشد.

• اگر \(f(midl) > f(midr)\): میتوان به راحتی گفت که \(midl < y\) است پس اگر در بازه \([L , R]\) عدد \(k\) وجود داشت در بازه \([midl , R]\) نیز وجود خواهد داشت.

• اگر \(f(midl) = f(midr)\): میتوان باز به راحتی گفت که \(midl < z\) است پس در بازه \([midl , R]\) قطعا عدد \(k\) مورد نظر وجود خواهد داشت زیرا در بازه \([L, R]\) وجود داشته است.

اگر حالت دوم رخ داده باشد نیز میتوان با استدلال مشابه گفت که هنوز مقدار \(k\) مناسب در بازه وجود خواهد داشت.

در این الگوریتیم اگر \(len = R - L\) تعریف کنیم و \(len^{\prime}\) را مقدار بعدی \(len\) قرار دهیم، میتوان گفت که \(len^{\prime} = \frac{2 * len}{3}\) است. و میتوان ثابت کرد که در حالت گسسته این الگوریتم از \(O(log(R-L))\) است. در حالت پیوسته نیز مانند حالت پیوسته باینری سرچ به تعدادی این کار را انجام میدهیم تا مطمعن باشیم تا \(6\) رقم اعشار درست حساب شده است که تعداد این بار ها از \(O(log((R-L)*10^{6}))\) است.

کد

int ask(double x) { // (1)!

    cout << "Ask: " << x << endl;

    int res;
    cin >> res;

    return res;
}

int main() {
    cout << fixed << setprecision(6);

    double L = 0, R = 1e9; // (2)!

    for (int i = 1; i <= 100; i++){ // (4)!
        double midl = (2 * L + R) / 3;
        double midr = (L + 2 * R) / 3;

        if (ask(midl) <= ask(midr)) L = midl;
        else R = midr;
    }

    cout << "Hads nahaei: " << R << endl; // (3)!
}

1. تابع ask در این جا نقش تابع \(f(x)\) را برای ما ایفا میکند و میتواند به جای آن هر تابعی ای با خواص \(f(x)\) باشد. همچنین میتواند خروجی \(f(x)\) به جای عدد صحیح عدد اعشاری باشد که در الگوریتم ما اهمیتی ندارد.

2. مقادیر \(L\) و \(R\) را چیزی قرار میدهیم که میدانیم شرایط گفته شده برقرار اند

3. در این حالت \(L\) با \(R\) فرقی ندارد و هردو جواب مسئله هستند

4. میتوان ثابت کرد که \(100\) مرحله برای گرفتن دقت مورد نظر کافی است.

توابع ++C

در ++C ما تابع lower_bound(a + l, a + r, x) را داریم که در یک آرایه سورت شده \(a\) به ما پوینتر اولین خانه در یک بازه که بزرگتر مساوی یک عدد دلخواه است را به ما میدهد که قابل تبدیل به اندیس آن خانه و مقدار آن خانه است.

int a[7] = {2, 3, 7, 7, 9, 10, 13};
int *x = lower_bound(a, a + 7, 5); // (1)!
int idx = lower_bound(a + 2, a + 7, 7) - a; // (2)!
int val = *lower_bound(a + 4, a + 6, 10); // (3)!

1. پوینتر اولین خانه بزرگتر مساوی \(5\) را در کل آرایه به ما میدهد (‌یعنی پوینتر خانه \(2\) آرایه).

2. اندیس اولین خانه بزرگتر مساوی \(7\) را در خانه های اندیس \(2\) تا اخر آرایه به ما میدهد (یعنی اندیس \(2\) را خروجی میدهد).

3. مقدار اولین خانه بزرگتر مساوی \(10\) را در خانه های اندیس \(4\) تا \(5\) به ما میدهد ( یعنی مقدار خانه \(5\) یعنی \(10\)).

همچنین ما تابع upper_bound(a + l, a + r, x) را داریم که مشابه lower_bound عمل میکند ولی به جای مقدار بزرگتر مساوی دنبال مقدار بزرگتر اکید میگردد و پیاده سازی آن نیز مشابه است.

int a[7] = {2, 3, 7, 7, 9, 10, 13};
int *x = upper_bound(a, a + 7, 5); // (1)!
int idx = upper_bound(a + 2, a + 7, 7) - a; // (2)!
int val = *upper_bound(a + 2, a + 6, 9); // (3)!

1. پوینتر اولین خانه بزرگتر \(5\) را در کل آرایه به ما میدهد (‌یعنی پوینتر خانه \(2\) آرایه).

2. اندیس اولین خانه بزرگتر \(7\) را در خانه های اندیس \(2\) تا اخر آرایه به ما میدهد (یعنی اندیس \(4\) را خروجی میدهد).

3. مقدار اولین خانه بزرگتر \(9\) را در خانه های اندیس \(2\) تا \(5\) به ما میدهد ( یعنی مقدار خانه \(5\) یعنی \(10\)).

همچنین میتوان توابع upper_bound و lower_bound را روی وکتور استفاده کرد

vector<int> a = {2, 3, 7, 7, 9, 10, 13};
vector<int>::iterator x = upper_bound(a.begin(), a.end(), 5); // (1)!
int idx = lower_bound(a.begin() + 2, a.end(), 7) - a.begin(); // (2)!
int val = *upper_bound(a.begin() + 2, a.begin() + 6, 9); // (3)!

1. پوینتر اولین خانه بزرگتر \(5\) را در کل آرایه به ما میدهد (‌یعنی پوینتر خانه \(2\) آرایه).

2. اندیس اولین خانه بزرگتر مساوی \(7\) را در خانه های اندیس \(2\) تا اخر آرایه به ما میدهد (یعنی اندیس \(2\) را خروجی میدهد).

3. مقدار اولین خانه بزرگتر \(9\) را در خانه های اندیس \(2\) تا \(5\) به ما میدهد ( یعنی مقدار خانه \(5\) یعنی \(10\)).

در نهایت میتوان به این دو تابع تابع cmp داد تا برای مقایسه به شیوه دیگری استفاده شود.

نکته

قبل از اینکه به توابع upper_bound و lower_bound تابع cmp را بدهیم بایستی آرایه را بر اساس تابع cmp سورت شده باشد.

می‌توانید به توابع upper_bound و lower_bound ورودی ای از جنسی به غیر از جنس آرایه هم بدهید! برای اینکار یا باید مقایسه‌ی این دو نوع تعریف شده باشد و یا تابع cmp بین این دو نوع تعریف شود.

bool cmp(int x, int y){
    return x > y; // (1)!
}

int main(){
    vector<int> a = {2, 3, 7, 7, 9, 10, 13}; // (2)!

    sort(a.begin(), a.end(), cmp); // (3)!

    int idx = lower_bound(a.begin(), a.end(), 5, cmp) - a.begin() // (4)!
}

1. قرار است این تابع از بزرگ به کوچک اعداد وکتور را سورت کند.

2. اعداد آرایه که در ابتدا طبق تابع cmp مرتب نشده اند.

3. اکنون اعداد آرایه به ترتیب مورد نظر سورت میشوند. بدین صورت که آرایه تبدیل به a = {13, 10, 9, 7, 7, 3, 2} میشود.

4. حال اندیس اولین خانه کوچکتر مساوی \(5\) را به دست می آوریم که برابر با \(5\) میباشد.

تعداد عملیات های این دو تابع نیز به ازای هربار استفاده برابر با \(O(log(n))\) است که \(n\) طول آرایه میباشد.

منابع بیشتر

• Binary search

• Lower bound

• Ternary Search

• Tutorial On Tof (Ternary Search) (ایده ای برای اینکه توابعی که کاملا ترنری سرچ پذیر نیستند را ترنری سرچ پذیر کنیم)

سوال ها

نیاز به عضویت در گروه شاززز!

برای حل برخی از سوالات باید ابتدا در گروه شاززز عضو شوید.

سوال	سختی	تگ ها	جاج
Guess The Number	800	Spoiler باینری سرچ	Oj.uz
فاصله گذاری اجتماعی	1300	Spoiler باینری سرچ	Shaazzz
Number Game	1400	Spoiler باینری سرچ الگوریتم های حریصانه	Codeforces
Fixed Point Guessing	1500	Spoiler باینری سرچ	Codeforces
Magic Powder 2	1500	Spoiler باینری سرچ الگوریتم های حریصانه	Codeforces
Vasya and String	1500	Spoiler باینری سرچ	Codeforces
Mafia	1600	Spoiler باینری سرچ	Codeforces
Hamburgers	1600	Spoiler باینری سرچ	Codeforces
Tree Infectoin	1600	Spoiler باینری سرچ الگوریتم های حریصانه	Codeforces
Keshi Is Throwing a Party	1600	Spoiler باینری سرچ الگوریتم های حریصانه	Codeforces
String game	1700	Spoiler باینری سرچ	Codeforces
Searching Local Minimum	1700	Spoiler باینری سرچ	Codeforces
Worm Worries - sub 1 - 2	1700	Spoiler باینری سرچ golden_ratio	Oj.uz
Increasing by Modulo	1700	Spoiler باینری سرچ	Codeforces
Renting bikes	1800	Spoiler باینری سرچ	Codeforces
Elevator	1800	Spoiler باینری سرچ	SGU
Multiplication Table	1800	Spoiler باینری سرچ	Codeforces
Multiplication Table	1800	Spoiler باینری سرچ	Codeforces
Read Time	1900	Spoiler باینری سرچ Two Pointers	Codeforces
Memory for Arrays	1900	Spoiler باینری سرچ	Codeforces
Guess The String	1900	Spoiler باینری سرچ	Codeforces
Castle Defense	2000	Spoiler باینری سرچ	Codeforces
Minimizing Difference	2000	Spoiler باینری سرچ Two Pointers الگوریتم های حریصانه	Codeforces
Interacdive Problem	2000	Spoiler باینری سرچ	Codeforces
Project Planning	2000	Spoiler باینری سرچ الگوریتم های حریصانه	Atcoder
Characteristics of Rectangles	2100	Spoiler باینری سرچ bitset	Codeforces
Degenerate Matrix	2100	Spoiler باینری سرچ	Codeforces
Guess The Maximums	2100	Spoiler باینری سرچ	Codeforces
GukiZ hates boxes	2200	Spoiler باینری سرچ الگوریتم های حریصانه	Codeforces
Professor GukiZ and Two Arrays	2200	Spoiler باینری سرچ	Codeforces
Weakness and Poorness	2200	Spoiler باینری سرچ	Codeforces
Restorer Distance	2200	Spoiler باینری سرچ	Codeforces
Median pyramid hard	2500	Spoiler باینری سرچ	Atcoder
Joking (Easy Version)	2500	Spoiler باینری سرچ	Codeforces
Worm Worries - sub 3 - 4	2700	Spoiler باینری سرچ	Oj.uz

نظرات