StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>A range in C or C++ is normally given as the pointing directly to the lower bound, but one past the upper bound. Unless you're feeling extremely masochistic, you probably want to stick to that convention in your search as well.</p> <p>Assuming you're going to follow that, your <code>last = midpoint-1;</code> is incorrect. Rather, you want to set last to one <em>past</em> the end of the range you're going to actually use, so it should be <code>last = midpoint;</code></p> <p>You also only really need <em>one</em> comparison, not two. In a binary search as long as the two bounds aren't equal, you're going to set either the lower or the upper bound to the center point, so you only need to do one comparison to decide which.</p> <p>At least by convention, in C++, you do all your comparisons using <code><</code> instead of <code><=</code>, <code>></code>, etc. Any of the above can work, but following the convention of using only <code><</code> keeps from imposing extra (unnecessary) requirements on contained types.</p> <p>Though most interviewers probably don't care, there's also a potential overflow when you do <code>midpoint = (left + right)/2;</code>. I'd generally prefer <code>midpoint = left + (right - left)/2;</code></p> <p>Edit: Though I'm hesitant to post a direct solution to what's openly stated as an interview question, I'll hope I can trust you to be honest in how you use this:</p> <pre><code>template <class T> T *lower_bound(T *left, T *right, T val) { while (left < right) { T *middle = left + (right - left) / 2; if (*middle < val) left = middle + 1; else right = middle; } return left; } template <class T> T *upper_bound(T *left, T *right, T val) { while (left < right) { T *middle = left + (right - left) / 2; if (val < *middle) right = middle; else left = middle + 1; } return left; } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload