Number Search (Most effecient)

Given that N is a random number (range 1 to 1000). We need to guess the N and for each guess, one of the following feedbacks may be given:

1. The guess is correct;
2. The guess is too large, so you should guess a smaller number;
3. The guess is too small, so you should guess a larger number.

In case 3, the value of N will increase by P, where P is another random number(range 1 to 200).

If the initial value of N=800 and P=150. You guess in the following sequence: Example

How do you code the following especially when it involves two number (N and P). I was thinking of using Binary Search but the it would be a problem if we do not know the value of P.

This is my code as of now :

myGuess=0;
checkCode=0;
int lower = 1, upper = 999;
myGuess = (lower+upper)/2;

do{
    if (checkCode == 2) {
    upper = myGuess - 1;
    }
else if (checkCode == 3){
    lower = myGuess + 1;
    upper += ran.nextInt(200);  //Need to guess the P value
    }

    myGuess = (lower+upper)/2;
}while(checkCode!=1);

Thanks