Be Like Hasib

Limits: 1s, 512 MB

Hasib, the famous programmer, uses a little game when he teaches Binary Search to his students. He requests them to guess a number between 1 to 100, and then he asks a few questions to them. After his students answer those questions, Hasib magically shouts the predicted number correctly!


This is a companion discussion topic for the original entry at https://toph.co/p/be-like-hasib

https://ideone.com/32Buck this code(Python) getting CPU limit, but same solution getting accepted while submit using C++. How can i reduce cpu usage?

@mhiceiuk Which Python are you using? Can you try using PyPy 3?

At first i submitted using python 3. Got CPU limit on 72 no test case. 2nd time i submitted using py py 3 but same results i got.

@mhiceiuk It looks like the issue is elsewhere.

So I downloaded your code and ran it on my computer with the test case where you are getting CPU Limited Exceeded. Before running it, inside the while loop, I added a print statement:

    else:
        hi = mid
    print(lo, hi)
print(cnt)

And, this is what I saw when I saw it:

499999999999999937 500000000000000000
499999999999999937 500000000000000000
499999999999999937 500000000000000000
499999999999999937 500000000000000000
499999999999999937 500000000000000000
499999999999999937 500000000000000000
499999999999999937 500000000000000000
499999999999999937 500000000000000000
499999999999999937 500000000000000000
499999999999999937 500000000000000000
499999999999999937 500000000000000000
499999999999999937 500000000000000000
499999999999999937 500000000000000000
499999999999999937 500000000000000000
499999999999999937 500000000000000000
499999999999999937 500000000000000000
^C
Traceback (most recent call last):
  File "ideone_32Buck.py", line 25, in <module>
    print(lo, hi)
KeyboardInterrupt

So, as you can see, your while loop is stuck with the same lo and hi values. Essentially you are getting an infinite loop for that particular case.

So you need to fix your binary search code. :slightly_smiling_face:

Which formula should be used to compute the middle element?
mid = L+(R-L)//2
This one takes one more or less guess to get the required value

my code is showing wa for 72th testcase. Where is the error?

#include<bits/stdc++.h>
using namespace std;

int main() {
int n,x,count=0;
cin >> n >> x;
int lo=1,hi=n,mid;
while(hi-lo>=1){
count++;
mid=(hi+lo)/2;
if(mid<x){
lo = mid+1;
}
else{
hi = mid;
}
}
cout << count;
return 0;
}