Minimum number of guesses needed to find a specific number

Objective– Given the numbers 1 to 1000, what is the minimum number of guesses needed to find a specific number if you are given the hint “higher” or “lower” for each guesses you make.

Naive Approach: Linear search

Start guessing from 1 and then 2 then 3  …till we do not find the answer.

Time complexity: O(N) , N  = total numbers, as per our problem it is 1000.

Better Approach: Binary Search

Start from N/2 and keep on discarding half elements after each guess based on the hint. Let’s understand from one example.

N = 1 to 1024, specific no = 378

1st guess = 512, hint = lower, new N =1 to 512, discard numbers 513 to 1024.
2nd guess = 256, hint = higher, new N =257 to 512, discard numbers 1 to 256
3rd guess = 385, hint = lower, new N = 257 to 384, discard numbers 385 to 512
4th guess = 320, hint = higher, new N = 321 to 384, discard numbers 257 to 320
5th guess = 352, hint = higher, new N = 353 to 384, discard numbers 321 to 352
6th guess = 368, hint = higher, new N = 369 to 384, discard numbers 353 to 368
7th guess = 376, hint= higher, new N = 377 to 384, discard numbers 369 to 376
8th guess = 380, hint= lower, new N = 377 to 380, discard numbers 381 to 384
9th guess = 378 MATCH found

Total no of guesses = 9

Java Code:

public class MinimumGuesses {
static void findMatch(int N, int x) {
int guesses = findMatchUtil(1, N, x);
System.out.println("No of guesses needed for N: " + N + " and x: " + x + " are: " + guesses);
}
static int findMatchUtil(int start, int end, int x) {
if (!(x >= start && x <= end)) {
//x is not in range,
return 1;
}
int guessCount = 0;
int guess = start + (end start) / 2;
guessCount++;
while (guess != x) {
//check the hint
if (guess > x) {
//need lower limit
end = guess;
} else {
//need higher limit
start = guess;
}
guess = start + (end start) / 2;
guessCount++;
}
return guessCount;
}
public static void main(String[] args) {
int N = 1024;
int x = 378;
findMatch(N, x);
}
}

view raw
MinimumGuesses.java
hosted with ❤ by GitHub

Output:
No of guesses needed for N: 1024 and x: 378 are: 9