adyyy's blog

Help with binary search!!
By adyyy, history, 5 years ago, In English

PLease someone help me with the binary search.... as I seen this far there never exists a single binary search technique for all the problems or may exists and I dont know . Anyways please help me if I have a function f(x) and i have to check for a k in [1 to n] such that f(k) is just >=m . f(x)=x*(x+1)/2; example n=9 m=22 ans=7; please tell someone..... P.S sorry for my poor english

  • Vote: I like it
  • -10
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Basically you have to find Lower Bound of 22 as per your example is concerned. If you understand Java, then go through this. It consists of the code of Lower Bound in Java. For C++, google about lower_bound function and for Python google about bisect.bisect_left function. These are in-built functions.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Well I know that but how to implement that with reference to a function... please read my blog again,,,

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

your code will be like that: bool f(x){return ((x * (x + 1) / 2 <= m)? 1:0)} ll d = 0, up = n; while(up — d > 1){ ll mid = (up + d) / 2; if(f(mid)){d = mid} else {up = mid} } cout << d; if you want a binary search problems for improve your skills you can send a message to me and i will give you my problems

→ Reply