reset password
Author Message
hal255
Posts: 51
Posted 22:11 Oct 22, 2014 |

Q10-16T #3

What is A? My instincts say it's 1. But if it is not, then please explain.

rabbott
Posts: 1649
Posted 22:15 Oct 22, 2014 |

I'd like to invite you to explain your reasoning and then see if anyone agrees or disagrees.

hal255
Posts: 51
Posted 22:25 Oct 22, 2014 |

Hmm... actually, I think I see where the code breaks it into 2 subproblems now. 

else if k < A[q] return BinarySearch(A, p, q-1, k)

            else return BinarySearch(A, q+1, r, k)

rabbott
Posts: 1649
Posted 22:43 Oct 22, 2014 |

The reason for the previous reply is that how you get an answer is much more important than the answer you get.

hal255
Posts: 51
Posted 22:58 Oct 22, 2014 |

Initially, I didn't see the "BinarySearch(A, p, q-1, k)"

I saw only "BinarySeach(A, q+1, r, k)". 

Since q = (p+r)/2, and if q+1 is passed into the new p, I didn't think this would break down the problem. So the size of problem is still the same, or may even throw us into an infinite loop since new P ( (p+r)/2 +1) is greater than old P (just P)... but now I know this isn't the case.

vsluong4
Posts: 87
Posted 23:02 Oct 22, 2014 |

The if-else statement in the pseudo code creates a branch, which means it will either execute if(THIS) or else(XOR THIS) but not both.

 

If it executed both the if AND the else then you would have 2 sub-problems (plus a broken programming language).  But this is not the case, it will only do one of those per branch encounter.  And since each branch is encountered only 1 time per call, we have only 1 sub problem generated each recursion.

vsluong4
Posts: 87
Posted 23:06 Oct 22, 2014 |

A more typical naming convention is >mid = (p+r)/2 because p is the left access index of the array and r is the right access index of the array.  mid(before we called it q) is the access index of the center of the array. 

Last edited by vsluong4 at 23:06 Oct 22, 2014.
hal255
Posts: 51
Posted 23:14 Oct 22, 2014 |

I didn't realize the IF statements break the problem into subproblems. I was too focused on the method calls and overlooked everything else. Thanks for the response.

vsluong4
Posts: 87
Posted 23:19 Oct 22, 2014 |

It doesn't break the sub-problem, it just makes it so it runs one (so 1 sub problem) the other the one (still 1 sub problem) but not both (not 2 sub-problems, so a != 2)

rabbott
Posts: 1649
Posted 11:32 Oct 23, 2014 |

Thanks Vince. Good answers and explanations.