c++ - Can some one help me figure out what I am doing wrong here? -

i working on problem leet code , question was:

you product manager , leading team develop new product. unfortunately, latest version of product fails quality check. since each version developed based on previous version, versions after bad version bad. suppose have n versions [1, 2, ..., n] , want find out first bad one, causes following ones bad. given api bool isbadversion(version) return whether version bad. implement function find first bad version. should minimize number of calls api.

the solutions had problem above was:

// forward declaration of isbadversion api. bool isbadversion(int version);  class solution  {     public:         int firstbadversion(int n)          {             bool x = isbadversion(n);             if (x == true)              {                 return n;             }             else             {                 return firstbadversion(n + 1);             }         } }; 

but on leet code says have wrong solution. please point me in right direction...

the explanation got leet code was:

input: 2 versions
          1 first bad version.
output: 2
expected: 1

your code find first bad version, on or after version passed in (n). in other words, depends on pass in.

i suspect what's passed in highest version (though specs aren't clear on this, makes sense), meaning you'll give highest version rather lowest one. better off (pseudo-code):

def findfirstbad(n):     = 1 n:         if isbadversion(i):             return     return sentinel # 0 or -1 or other na response. 

in case, minimising api calls need use of binary search algorithm, should investigate. have recursive linear search not minimise number of calls.

whereas linear search removes 1 possible item on each iteration (or recursion), binary search remove half remaining space each time. pseudo-code go like:

def findfirstbad(n):     # no bad version possible if no versions.      if n < 1:         return sentinel      # start pincer @ ends.      lastgood = 0     firstbad = n      # continue until lastgood , firstbad together.      while lastgood + 1 < firstbad:         # find midpoint, adjust correct pincer.          mid = (lastgood + firstbad) / 2         if isbadversion(mid):             firstbad = mid         else:             lastgood = mid      # ensure 1 last check in case there no bad versions.      if isbadversion(firstbad):         return firstbad     return sentinel 

if run code in head assistance of pen , paper, you'll see gradually brings in lastgood/firstbad indexes until locates first bad 1 (or discovers there is no bad one).

then simple check decide whether you've found or not, , return version if have found it.