Блог пользователя adyyy

Help with binary search!!
Автор adyyy, история, 5 лет назад, По-английски

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

  • Проголосовать: нравится
  • -10
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

    → Ответить
»
5 лет назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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

→ Ответить