**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 1^{st}guess = 512, hint = lower, new N =1 to 512, discard numbers 513 to 1024. 2^{nd}guess = 256, hint = higher, new N =257 to 512, discard numbers 1 to 256 3^{rd}guess = 385, hint = lower, new N = 257 to 384, discard numbers 385 to 512 4^{th}guess = 320, hint = higher, new N = 321 to 384, discard numbers 257 to 320 5^{th}guess = 352, hint = higher, new N = 353 to 384, discard numbers 321 to 352 6^{th}guess = 368, hint = higher, new N = 369 to 384, discard numbers 353 to 368 7^{th}guess = 376, hint= higher, new N = 377 to 384, discard numbers 369 to 376 8^{th}guess = 380, hint= lower, new N = 377 to 380, discard numbers 381 to 384 9^{th}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); | |

} | |

} |

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