**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**:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

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