374. Guess Number Higher or Lower
Problem Description
In the Guess Game, you have to guess a number chosen by the game from a range of numbers starting from 1
to n
. The game's goal is to find the number selected by the game with the help of a clue provided after each guess. When you make a guess by choosing a number within the range, the game responds by indicating if your guess is higher, lower, or equal to the secret number it has chosen. The responses are given through a pre-defined guess
function with the following possible return values:
- If your guess is too high, the function returns
-1
. - If your guess is too low, the function returns
1
. - If your guess is correct, meaning it matches the secret number, the function returns
0
.
Your task is to use this guess
function to determine and return the secret number the game has picked.
Intuition
The straightforward approach to solving this problem would involve using a binary search method. Since the potential numbers range from 1
to n
, we can start by guessing in the middle of this range. Depending on the feedback from the guess
function, we would know if the target number is higher or lower than our current guess, and we would adjust our search range accordingly, narrowing it down until we find the exact number.
However, this solution uses a specialized Python library called bisect
that is capable of performing binary search operations efficiently. Here's the intuition behind the approach in the solution provided:
bisect.bisect
: This is a function from thebisect
module which is used to find a position in a list where an element should be inserted to keep the list sorted.- Since we know the
guess
function returns-1
if our guess is high and1
if our guess is low, we can use this information as a key function for thebisect
method. By negating theguess
function in the key, we essentially transform theguess
function’s return value to use it forbisect
. - The
range
function generates a sequence of numbers, which represents our possible guesses. - By using
bisect
with the negatedguess
as a key, it will effectively perform a binary search to find the correct position, i.e., where the return value of theguess
function would be0
, which means the guess matches the picked number.
In doing so, the solution code bypasses the more common iterative or recursive implementations of binary search and instead uses the bisect
library to find the solution, showing yet another powerful aspect of Python's standard library.
Learn more about Binary Search patterns.
Solution Approach
The implementation of the provided solution uses the bisect
module from Python, which is designed to make binary searches simple and efficient. Here's the breakdown of the solution approach:
-
Leveraging Python's Standard Library: The
bisect
module contains two main functions —bisect_left
andbisect_right
(or justbisect
as an alias forbisect_right
), which are used for binary search. -
Understanding the bisect function: The
bisect.bisect
function is used to find the insertion point for a given element in a sorted list to maintain the sorted order. This means that it can be used to find where in the list a new element should go such that the list will still be in order. -
Applying bisect with a key function: In this problem, the
bisect
function is given a key argument, which is a function that will be called on each element in the array before making comparisons during the binary search. Here, the key function is a lambda function that returns the negated result of theguess
function:lambda x: -guess(x)
. The negation is useful becausebisect
is typically used for finding insertion points and expects the condition to be sorted in ascending order. Since a correct guess returns0
, when we negate0
, it remains0
, whichbisect
would interpret as the correct insertion point or, in our case, the correctly guessed number. -
Using the range: The
range
function,range(1, n + 1)
, creates a sequence of numbers starting from1
ton
. This range represents the entire list of potential guesses. -
Finding the correct guess: The
bisect.bisect
function is called with the range and key function defined above. It will effectively perform a binary search over this range, using the key function to compare the guess to the secret number until the insertion point (where the guess is correct) is located. -
Returning the correct number: The function will return the position where the
guess(x)
is0
, which is the selected number.
The algorithm used in this solution has an average-case and worst-case time complexity of O(log n) because it is a binary search algorithm. It works by essentially cutting down the search space by half with each incorrect guess that it makes, thereby narrowing in on the correct number with each iteration.
Overall, this is an elegant approach that takes full advantage of Python's capabilities, providing an alternative to the more manually implemented binary search algorithm.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's assume the secret number the game has picked is 6
and our range n
is 10
. We will use the provided solution approach leveraging the bisect
module to find this secret number.
-
Setting Up the Problem: The game has chosen a secret number from
1
to10
, and our guess should be within this range. Let's illustrate the binary search mechanism step by step. -
First Iteration: The middle of our range
1
to10
is5.5
(we would round this to6
in implementation, but let's follow the strict binary process). We guess5
as our first attempt (since we typically use integer division which truncates the decimal). Theguess
function returns1
since our guess is lower than the secret number. -
Adjusting the Range: With the feedback that our guess was too low, we adjust our range from
6
to10
. The new middle of this range is8
. -
Second Iteration: We now guess
8
, and theguess
function returns-1
indicating our guess is higher than the secret number. -
Narrowing Down Further: The secret number is, therefore, between
6
and7
(since we've ruled out8
and above). The new middle point is6.5
, so our next guess will be6
. -
Third Iteration and Correct Guess: Guessing
6
, theguess
function returns0
, signalling that we've found the correct number.
Throughout this process, if we were using bisect.bisect
with the negated guess
function as the key, it would have negated the return values of the guess
function and performed these steps internally. We wouldn't actually see the returned values of 1
or -1
; bisect
would use them to perform the binary search:
- At the first iteration, with the middle element as
5
and theguess
function returning1
(guess too low), negating it gives us-1
, which guides the search to go higher. - At the second iteration, with the middle element as
8
and theguess
function returning-1
(guess too high), negating it gives us1
, which guides the search to go lower. - Finally, at the correct guess
6
, theguess
function returns0
, and negated or not, it remains0
, indicating the correct position has been found.
So with the bisect.bisect
function, the correct number 6
would be returned as the position where the guess(x)
equates to 0
. This example walkthrough illustrates how the binary search and, by extension, the bisect
function would find the secret number chosen by the game.
Solution Implementation
1# The guess API is already defined for you.
2# @param num, your guess
3# @return -1 if num is higher than the picked number
4# 1 if num is lower than the picked number
5# otherwise return 0
6# def guess(num: int) -> int:
7
8import bisect
9
10class Solution:
11 def guessNumber(self, n: int) -> int:
12 # Use binary search to find the guessed number.
13 # Define the bisect function to compare guess results.
14 def guess_compare(x):
15 # Return the result of the guess API call:
16 # Negative result if our guess is higher (-1),
17 # Positive if our guess is lower (1),
18 # Zero if our guess is correct (0)
19 return -guess(x)
20
21 # Use the bisect function to find the correct number.
22 # We make use of the `key` parameter to provide our custom comparison
23 # function which uses the guess API as the comparison logic.
24 return bisect.bisect_left(range(1, n + 1), 0, key=guess_compare) + 1
25
26# Note: The original implementation used bisect.bisect, which by default assumes
27# an insertion point that would maintain order. In this case, we want the exact position
28# where the guess result is 0, hence bisect_left is more appropriate.
29
1/**
2 * This class is an extension of the GuessGame class which contains a guess API method.
3 * The guessNumber method aims to find the number which the API is thinking of.
4 */
5public class Solution extends GuessGame {
6 /**
7 * Guesses the number by using binary search to minimize the number of calls to the guess API.
8 *
9 * @param n the upper bound of the range to search.
10 * @return the number that matches the guess API's hidden number.
11 */
12 public int guessNumber(int n) {
13 // Initialize the lower bound of the search range.
14 int left = 1;
15 // Initialize the upper bound of the search range.
16 int right = n;
17
18 // Continue searching as long as the range has not been narrowed down to a single element.
19 while (left < right) {
20 // Calculate the midpoint of the current range to use as our guess.
21 int mid = left + (right - left) / 2;
22
23 // Make a guess using the midpoint and get the response from the guess API.
24 int apiResponse = guess(mid);
25
26 // If the guess is too high or correct, narrow the range to the lower half (inclusive of mid).
27 if (apiResponse <= 0) {
28 right = mid;
29 } else {
30 // If the guess is too low, narrow the range to the upper half (exclusive of mid).
31 left = mid + 1;
32 }
33 }
34 // When the loop exits, left and right converge to the target number; return it.
35 return left;
36 }
37}
38
1/**
2 * The guessNumber function tries to find a secret number within a range between 1 and n.
3 * It relies on a pre-defined API "guess" which takes an integer as an input (your guess) and returns
4 * -1 if the guess is lower than the secret number, 1 if it is higher, and 0 when your guess matches the secret number.
5 *
6 * @param n An integer representing the upper bound of the range within which to guess the number.
7 * @return The secret number.
8 */
9
10class Solution {
11public:
12 int guessNumber(int n) {
13 int lowerBound = 1; // Initialize lower bound of the search interval
14 int upperBound = n; // Initialize upper bound of the search interval
15
16 // Perform a binary search in the interval from lowerBound to upperBound
17 while (lowerBound < upperBound) {
18 // Calculate the middle value in the current interval
19 int mid = lowerBound + ((upperBound - lowerBound) >> 1); // Equivalent to (lowerBound + upperBound) / 2 but avoids overflow
20
21 // Use the guess API method to compare the middle value with the secret number
22 if (guess(mid) <= 0) {
23 // If the guess is greater than or equal to the secret number, narrow the search to the lower half
24 upperBound = mid;
25 } else {
26 // If the guess is less than the secret number, narrow the search to the upper half
27 lowerBound = mid + 1;
28 }
29 }
30
31 // At this point, lowerBound == upperBound, and we have found the secret number
32 return lowerBound;
33 }
34};
35
1// Forward declaration of the guess API.
2// @param {number} num - Your guess
3// @return -1 if num is lower than the guess number
4// @return 1 if num is higher than the guess number
5// @return 0 if num is the guess number
6declare function guess(num: number): number;
7
8/**
9 * Finds the number guessed by the guess API within the range [1, n].
10 *
11 * @param {number} n - The maximum range within which the guessed number falls.
12 * @return {number} - The correct guessed number.
13 */
14function guessNumber(n: number): number {
15 // Initialize the search range
16 let left = 1;
17 let right = n;
18
19 // Use binary search to find the guessed number
20 while (left < right) {
21 // Calculate the midpoint to minimize the search range
22 // Using right shift by 1 to ensure no overflow happens
23 const mid = left + ((right - left) >>> 1);
24
25 // Guess the middle of the range and reduce the range based on the response
26 const result = guess(mid);
27 if (result <= 0) {
28 // If the guessed number is less than or equal to mid, narrow the range to the left half
29 right = mid;
30 } else {
31 // If the guessed number is greater than mid, narrow the range to the right half
32 left = mid + 1;
33 }
34 }
35 // At the end of the loop, left should be equal to the guessed number
36 return left;
37}
38
Time and Space Complexity
The time complexity of the provided code is O(log n)
. This is because the bisect
function employed here uses a binary search algorithm to find the insertion point for 0
in the sorted sequence. It repeatedly divides the sequence in half to locate the position, which results in a logarithmic number of steps with respect to the sequence's length.
The space complexity of the code is O(1)
since it uses a constant amount of extra space. The key
function in the bisect
function does not store any additional data structures related to the size of the input n
, and the rest of the operations do not require more space that grows with the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
How many ways can you arrange the three letters A, B and C?
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.