Boshkash_Hates_CP's blog

Binary Search Indetification
By Boshkash_Hates_CP, history, 2 months ago, In English

Hello , when solving problems on binary search, i solve them because i know that i'm solving problems on Binary search topic , but if i come to a problem statement i don't know how or even if I should use binary search or not ... so my question is , how to make sure you're solving a binary search problem?

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

solve more problems, work on more ideas, see the editorial. after some months you will be able to identify it.

→ Reply
»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

You should read about monotonic functions and try to find patterns similar to it. Also finding minimum or maximum value type problems may involve binary search on answer.

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    so if the problem defined on a function fn such that fn is a monotonic (either increases or decreases in one direction) the first thing i should think about is BS , any other notices...?

    → Reply
»
2 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Tbh I still couldn't identify Binary search. My entire intuition of bs is "if it looks like dp, but constraints do not support dp and couldn't prove greedy then it must be binary search" and it works almost all the time.

→ Reply
  • »
    »
    2 months ago, # ^ |
    ← Rev. 3   Vote: I like it +1 Vote: I do not like it

    that some crazy identification of bs but IDK i get bs ideas intutively like I solved a problem today I almost instantly recognized it is bs after sorting in non increasing order

    → Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    well, that's kinda nice , how do you check for dp constraints and how to prove the greedy?

    → Reply
»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

If some function is monotonic and you want to know the equal range of some value you should use binary search.

Why would you try to identify a problem is binary search or not? Just be ready to apply binary search whenever you noticed such a function.

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yeah , okay but how do you mean by "you want to know the equal range of some value"?

    → Reply
»
2 months ago, # |
  Vote: I like it +11 Vote: I do not like it

I apply binary search when i notice a pattern of TT..TF..FF or F..FTT..T .

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i don't get the pattern ...

    → Reply
    • »
      »
      »
      2 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      After a point it is always true or false. You can use BS to find that point... This is a kind of monotonicity pattern mostly used in problems where you need to apply BS on Answer.

      → Reply
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I'll give you an exemple

      Question: find the first element higher or equal to 3 in a=[ 1,2, 4, 6, 10 ].

      long story short , i want to find the index i where a[i-1]<3 and 3<=a[i].

      I'm going to think of a new array b such that if a[i]<x , b[i]=False else b[i]=True

      we will get b=[ F, F, T, T, T ] and the answer will be the element in 'a' where the elements in 'b' transitioned from False to True

      binary search will be able to find answer (which is 3) in log(n)

      here is a better explanation by Errichto

      → Reply
»
2 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

One trick you can find in some problems is trying to find a number (often the minimum or the maximum) that works for a certain dataset, and you can verify if a certain number works in O(1) or O(n) (or different depending on the problem and input size).

I'll use this leetcode problem as an example.

You can verify if a certain amount of seconds works with an O(n) operation, and since the function is monotonic, you can simply search for the minimum value that works and return that.

(this doesn't apply to all problems, but it should hopefully be helpful)

→ Reply
»
2 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Binary Search works when a function $$$f$$$ is increasing/decreasing (sorted in increasing/decreasing way) on $$$\mathbb{R}$$$ in general case , so if you've a computational complexity of $$$\mathcal{O}(f')$$$ for $$$f$$$ then you can apply binary search on $$$\mathcal{O}(f' \times \log(|r-l|)$$$ that's we apply binary search on range $$$[l,r]$$$.

However in some case this defintion can be optimized by some optimizations such as precalculation , for example :

Given an array $$$a$$$ of $$$a_1,a_2,..,a_n$$$ , find any subarray of sum $$$x$$$

Spoiler

Example 2

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

if there is a point where over it a constraint is met and under it a constraint is not met and you want to find the point its bs so the easiest version of this is searching a sorted array for x if md<x that is a constraint that is met and if x<=md that is constraint is not met

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Boshkaskh Ma7foz

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I used to struggle with this exact situation. And now I made a thumb rule, that if I don't get the idea of the problem maybe within 5-10 minutes. I try to finding if I can apply binary search the answer in some way. This helped me a lot, as sometimes it unexpectedly hit me where the solution was not very obvious.

And usually, there are two things to address when searching for the solution: 1. Can you reduce your search space drastically if you can verify that a given k works for you. 2. Is checking for a given k can be done in O(n) or O(n logn) or anything below O(n^2). Although, it highly depends on the context of the problem, but this is a good point to think.

I hope this help you in some way.

→ Reply