💻
Algorithm
  • README
  • Array
    • At Most To Equal
    • Count Inversions In An Array
    • Interleaving Placement
    • Kadane
    • Left To Right State Transition
    • Permutation
    • Quick Select
    • Sliding Window
    • Two Pointers
  • Binary Tree
    • Avl Tree
    • Binary Search Tree
    • Serialization And Deserialization
    • Traversal
  • Company
    • Facebook
  • Cpp
    • Array
    • Memset 3 F
    • Overflow
  • Data Structure
    • Binary Indexed Tree
    • Segment Tree And Binary Index Tree
    • Segment Tree
    • Stack
    • Trie
    • Union Find
  • Dynamic Programming
    • Knapsack
      • 0 1 Knapsack
      • Bounded Knapsack
      • Unbounded Knapsack
    • Bitmask Dp
    • Dp On Subsets
    • Dp On Tree
    • Dp With Sorting
    • Selective State Dp
    • Travelling Salesperson
  • Graph
    • Minimum Spanning Tree
      • Kruskal
      • Prim
    • Shortest Path
      • Bellman Ford
      • Dijkstra
      • Floyd Warshall
      • Johnson
      • Shortest Path Faster Algorithm
    • Bi Directional Breadth First Search
    • Bipartite
    • Breadth First Search
    • Component Coloring
    • Component Count
    • Depth First Search
    • Eulerian Path
    • Maximum Bipartite Matching
    • Tarjan
    • Topological Sort
    • Tree Diameter
    • Tree Ring Order Traversal
  • Greedy
    • Greedy Scheduling
    • Regret Greedy
  • Math
    • Catalan Number
    • Combinatorics
    • Factorial
    • Factorization
    • Fast Pow
    • Gcd
    • Geometry
    • Get Digits
    • Lcm
    • Median Minimizes Sum Of Absolute Deviations
    • Mode
    • Modular Multiplicative Inverse
    • Palindrome
    • Prime Number
    • Round Up
    • Sieve Of Eratosthenes
    • Stars And Bars
    • Sum Of Sequence
  • Miscellaneous
    • Bin Packing
    • Floyds Tortoise And Hare
    • Hungarian
    • Palindrome
  • Sort
    • Bubble Sort
    • Cycle Sort
    • Heap Sort
    • Merge Sort
    • Quick Sort
    • Sorting
  • Stl
    • Cpp Stl
    • Istringstream
    • Lower Bound Upper Bound
    • Priority Queue
  • String
    • Kmp
    • Manacher
    • Rabin Karp
    • String Processing
    • Z
  • Backtracking
  • Binary Answer
  • Binary Lifting
  • Binary Search
  • Bit Manipulation
  • Date
  • Difference Array
  • Discretization
  • Divide And Conquer
  • Gray Code
  • Great Problems For Practice
  • Interval Scheduling Maximization
  • Io Optimization
  • K Subset Partitioning
  • Line Sweep
  • Longest Common Subsequence
  • Longest Increasing Subsequence
  • Meet In The Middle
  • Minmax
  • Mono Deque
  • Monotonic Stack
  • Offline Query
  • P And Np
  • Prefix State Map
  • Prefix Sum
  • Random
  • Reservoir Sampling
  • Reverse Polish Notation
  • Sqrt Decomposition
Powered by GitBook
On this page
  • What's Binary Answer
  • When can we use Binary Answer?
  • Algorithm
  • Pseudo Code
  • Problems

Was this helpful?

Binary Answer

PreviousBacktrackingNextBinary Lifting

Last updated 3 years ago

Was this helpful?

What's Binary Answer

When the search range is small, the binary answer problems are solvable by linear scaning the answer range. For example, assume the answer range is [0, 100], we can check 0, then 1, ..., then 100, and we return the maximum number that is valid.

However, when the answer range is large, say [0, 10^5], linear scanning the entire answer range will get TLE.

So, instead of doing O(N) linear scanning, we binary search in the answer range which reduces the time complexity to O(logN).

When can we use Binary Answer?

We can use "Binary Answer" solution if we can write a predicate function valid(i) that has monotocity:

  • If valid(i) == true, then valid(j) == true for all j <= i.

  • If valid(i) == false, then valid(j) == false for all j >= i.

Algorithm

Our goal is the find the maximum i that valid(i) == true.

We can use two pointers L = minVal, R = maxVal, and keep using binary search to move the pointers towards each other until they swap order. In the end, R will point to the largest value that is valid, L will point to the smallest value that is invalid.

Pseudo Code

Assume the answer range is monotonically going from valid to invalid, and we are looking for the maximum valid value.

int L = minVal, R = maxVal
while (L <= R) {
    int M = (L + R) / 2;
    if (valid(M)) L = M + 1;
    else R = M - 1;
}
return R >= minVal ? R : NOT_FOUND;

If we are looking for the minimal invalid value, simply return L <= maxVal ? L : NOT_FOUND.

Problems

410. Split Array Largest Sum (Hard)
668. Kth Smallest Number in Multiplication Table (Hard)
718. Maximum Length of Repeated Subarray (Medium)
719. Find K-th Smallest Pair Distance (Hard)
778. Swim in Rising Water (Hard)
1044. Longest Duplicate Substring (Hard)
1062. Longest Repeating Substring (Medium)
1283. Find the Smallest Divisor Given a Threshold (Medium)
1300. Sum of Mutated Array Closest to Target (Medium)
1482. Minimum Number of Days to Make m Bouquets (Medium)
1648. Sell Diminishing-Valued Colored Balls (Medium)
1802. Maximum Value at a Given Index in a Bounded Array (Medium)
1870. Minimum Speed to Arrive on Time (Medium)