แนวคิด
สมมติว่าเล่น Guess Game คุณสมบัติเกม:
- ผู้เล่น 1 เลือกตัวเลข 1 ถึง n
- ผู้เล่น 2 ทายว่าผู้เล่น 1 เลือกอะไร
- ทุกครั้งที่ทายผิด ผู้เล่น 1 จะบอกว่าตัวเลขสูงกว่าหรือต่ำกว่า
ใช้ฟังก์ชัน guess(num) คืนค่า 3 ผลลัพธ์:
- -1: ตัวเลขของผู้เล่น 1 ต่ำกว่า
- 1: ตัวเลขของผู้เล่น 1 สูงกว่า
- 0: ตรงกัน
เช่น ถ้าอินพุตคือ n = 10, pick = 5 ผลลัพธ์คือ 5
วิธีแก้:
- l := 1, r := n
- while l <= r: m := l+(r-l)/2, ถ้า guess(m) เท่ากับ 0: คืนค่า m, ถ้า guess(m) เท่ากับ -1: r := m-1, มิฉะนั้น: l := m+1
- คืนค่า 0
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
int number;
int guess(int num){
if(number > num) return 1;
if(number < num) return -1;
return 0;
}
public:
Solution(int n){ number = n; }
int guessNumber(int n) {
int l=1,r=n,m;
while(l<=r){
m=l+(r-l)/2;
if(guess(m)==0) return m;
if(guess(m)==-1) r=m-1;
else l=m+1;
}
return 0;
}
};
main() {
Solution ob(5); // pick = 5
cout << (ob.guessNumber(10));
}
อินพุต
5,10
เอาต์พุต
5
