LeetCode 75
Guess Number Higher or Lower
- Problem
- LC 374
- Topic
- Binary Search
- File
- official75_LC374GuessNumberHigherOrLower.java
- Path
- pkg5leetcode/official75/official75_LC374GuessNumberHigherOrLower.java
- Package
- pkg5leetcode.official75
- Command
- java pkg5leetcode/official75/official75_LC374GuessNumberHigherOrLower.java
- Approach
- Binary search on answer range.
- Complexity
- Time O(log n), Space O(1)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.official75;2 3/*4 * Guess Number Higher or Lower | LC 3745 * APPROACH: Binary search on answer range.6 * COMPLEXITY: Time O(log n), Space O(1)7 */8public class official75_LC374GuessNumberHigherOrLower {9 static int pick = 6;10 11 static int guess(int num) {12 return Integer.compare(pick, num);13 }14 15 static int guessNumber(int n) {16 int lo = 1, hi = n;17 while (lo <= hi) {18 int mid = lo + (hi - lo) / 2;19 int g = guess(mid);20 if (g == 0) return mid;21 if (g < 0) hi = mid - 1;22 else lo = mid + 1;23 }24 return lo;25 }26 27 public static void main(String[] args) {28 pick = 6;29 check(guessNumber(10) == 6, "case1");30 pick = 1;31 check(guessNumber(1) == 1, "case2");32 System.out.println("all tests passed");33 }34 35 static void check(boolean cond, String name) {36 if (!cond) throw new AssertionError("FAILED: " + name);37 System.out.println(" PASS " + name);38 }39}