yogomate's blog

how do i to convert recursion code to for/while loop
By yogomate, history, 15 months ago, In English

here i have a recursion code specifically a binary search code(recurion) ll bs(ll l, ll h, vector wins[], ll k, ll i)// { if(l<=h) { ll m=(l+h)/2;

if(wins[i][m]<=k){
        if(m+1<=h){
            if(wins[i][m+1]<=k){
                return bs(m+1, h, wins, k, i);
            }else{
                return m+1;
            }
        }else{
            return m+1;
        }
    }else{
        return bs(l, m-1, wins, k, i);
    }
}else{
    return 0;
}

} and i converted it to while loop binary search but i am not getting desired output my code : ll binary(vector wincnt, ll player, vector rounds[], ll k){ int ans = 0; ll l = 0; ll r = wincnt[player]-1; while(l <= r){ int mid = l + (r — l) / 2; if(mid+1<=r){ if(rounds[player][mid+1]<=k){ l = mid+1; }else{ return m+1; } } else{ r = mid-1; } } return ans; } what did i do wrong

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

Comments Comments (1)
| Write comment?
»
15 months ago, # |
  Vote: I like it +5 Vote: I do not like it

I don't normally code in C++ so I took the liberty of making a slight change, in the function $$$binary$$$, instead of passing the array of vectors $$$rounds$$$, I have passed the vector $$$rounds[player]$$$ instead, calling it $$$rounds$$$ anyway.

Why did I do so? When passing around vectors into functions, it's best to do so by reference, as otherwise, the whole vector gets copied which can at times lead to TLE (it did in this case). This was happening if your given function signature was to be followed, and I couldn't exactly fix that properly, courtesy of being a Java coder myself.

Getting to the main part of the issue ->

You skipped the outermost condition where you were checking $$$rounds[player][mid] <= k$$$ in your while loop, so it botched everything up. I simply fixed that and made some minor fixes (basically translated your recursion into iterative form, line by line, and it worked).

Edited Submission

function
→ Reply